Filling The Prefix Table
pi[i] is the length of the longest proper prefix of s[0..i] that is also a suffix of s[0..i].
For s = "ababcabab" three entries are missing:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| s[i] | a | b | a | b | c | a | b | a | b |
| pi[i] | 0 | 0 | 1 | 2 | ? | 1 | 2 | ? | ? |
What are pi[4], pi[7] and pi[8]?
Sign in to answer questions and track your progress
Sign In