AlgoScope

Prefix Function

For each prefix, the length of its longest proper prefix that is also a suffix, built by falling back through shorter borders.

String algorithms, algorithm, intermediateAlso called failure function, LPS array
pi of 1 is 0.patpiababac00
pi of 1 is 0.patpiababac00

String Matching: Prefix function of a pattern

Decision, step 2 of 7

i = 1, prefix "ab". Start from pi[0] = 0. No border can be extended, so pi[1] = 0.

How string matching works

Cost

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

Before this

Leads to

Topics that need this one first.

Taught by the same lesson

String Matching covers these too, in the same run.