complexitysearchingstrings
Why does KMP use a prefix table?
Anonymous
The prefix table records the longest proper prefix of each pattern prefix that is also its suffix. On a mismatch, that tells KMP where to resume in the pattern without moving backward through the text. For text length n and pattern length m, the search takes O(n + m) time and uses O(m) extra space.
0