AlgoScope

Knuth-Morris-Pratt

On a mismatch, drop j to pi[j - 1] so the pattern slides without re-reading any text character.

String algorithms, algorithm, intermediateAlso called KMP
Character 0 matches.txtpatpiabcabcabdabcabd000120a = a

String Matching: KMP, no re-reading

Decision, step 2 of 11

'a' matches pattern[0], j = 1.

How string matching works

Cost

Best
O(n + m)
Average
O(n + m)
Worst
O(n + m)
Space
O(m)

Leads to

Topics that need this one first.

Taught by the same lesson

String Matching covers these too, in the same run.