gno.land/p/moul/x/daily/kmp/v0

Knuth–Morris–Pratt substring search — Index, Contains, FindAll, Count, Table, MaxPattern.

1import "gno.land/p/moul/x/daily/kmp/v0"
2
3kmp.Index("mississippi", "issi")   // 1
4kmp.FindAll("mississippi", "issi") // [1 4] — overlapping
5kmp.Count("aaaa", "aa")            // 3
6kmp.Table("ababaa")                // [0 0 1 2 3 1]

The naive scan re-compares characters it already matched, so "aaaaaaab" inside "aaaaaaaaaaaaaaab" costs O(n·m). KMP precomputes a failure table and slides the pattern without ever moving the text cursor backwards: O(n+m), with no bad case. On chain that matters — a pathological input is an attack, not bad luck.

Two things worth knowing, each with a test:

• FindAll reports overlapping matches. FindAll("aaaa", "aa") is [0 1 2], not [0 2] — the honest reading of "every occurrence". A caller wanting disjoint matches can filter; one wanting overlap could not recover it.
• Offsets are BYTE offsets, not runes. gno strings are UTF-8, so Index("éx", "x") is 2. That matches strings.Index, and it is the right unit for slicing.

Index is pinned against strings.Index across a spread of inputs: same contract, different algorithm.

Live demo: r/moul/x/daily/kmpdemo · render it at /r/moul/x/daily/kmpdemo/v0.

Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.

🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.