Skip to content Search Apps Documentation Source Content File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

Knuth–Morris–Pratt

Linear-time substring search, demoing the p/moul/x/daily/kmp library.

Failure table

For each prefix of issi, the length of the longest proper prefix that is also a suffix. This is what lets the scan slide the pattern without ever rewinding the text.

i prefix table
0 i 0
1 is 0
2 iss 0
3 issi 1

Searching

issi in mississippi:

mississippi
 ^^^^
    ^^^^

Matches at 1, 4 — overlapping, and Count agrees: 2.

Overlap is deliberate

FindAll("aaaa", "aa") returns 0, 1, 2, not just the disjoint ones — "every occurrence" read honestly. A caller wanting disjoint matches can filter; one wanting overlap could not recover it.

Why it belongs on chain

The naive scan is O(n·m): aaaaaaaab inside aaaaaaaaaaaaaaaab re-compares everything it already matched. KMP is O(n+m) with no bad case, so a pathological input is not an attack.