Embed Notice

Tangentially related to DFAs is the KMP String-Searching Algorithm. Which locates the first index (or all indices) of a "needle" text in a "haystack" text.

The naive way is to iterate over each index & check if its an answer, which takes O(n*m) time! We can achieve the task in O(n+m) time via the KMP Algorithm!

Iterate over the needle to find where its prefix reoccurs, storing results in a table. After the end of the prefix, consult the in-progress table for previous prefixes to check.

1'/2'