The Prefix Function
Intermediate
For each position i of s, return the length of the longest proper prefix of s[:i + 1] that is also a suffix of it (proper: shorter than the whole piece).
For "abcabca" the answer is [0, 0, 0, 1, 2, 3, 4].
The starter code tries every length at every position. It is correct but too slow for long strings.
Examples
Example 1
Input:
prefix_function('abcabca')
Output:
[0, 0, 0, 1, 2, 3, 4]
Example 2
Input:
prefix_function('aaaa')
Output:
[0, 1, 2, 3]
Constraints
0 <= len(s) <= 200000- Lower-case letters.
Theory
Go to TheoryKeywords
dsa-sheetadvanced-stringspattern-matching
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.