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.

README.md

1.99 Kb · 44 lines
Download

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.