Sign in to watch this lesson
Advanced - Strings Ā· 4:59
Prefix-Function Automaton and Applications
The prefix function does far more than drive KMP. We count how often every prefix of a string occurs by pushing counts down the border chain, read the shortest repeating unit straight off the last value, and turn the table into a full automaton whose missing transitions are copied from earlier rows in O(26 n). Then the automaton counts pattern matches inside Gray strings with 2^60 characters by storing what each half does to every state.
You will learn
- Count the occurrences of every prefix of s in O(n): tally pi values, push counts down the border chain from long to short, then add one
- Find the shortest repeating unit of a string with k = n - pi[n-1], and explain why the unit is k only when k divides n
- Build the prefix-function automaton on s + '#' in O(26 n) by copying the row of pi[i-1] for every non-matching letter, and know its memory cost
- Count matches inside huge implicit strings (Gray strings) with per-level tables G[i][j] and K[i][j] instead of reading 2^k characters