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

Aho-Corasick multi-pattern search over strings, every overlapping match in one pass: New, FindAll, FindFirst, Contains, Patterns, Nodes.

1import "gno.land/p/moul/x/daily/ahocorasick/v0"
2
3m := ahocorasick.New([]string{"he", "she", "his", "hers"})
4m.FindAll("ushers")   // she@1, he@2, hers@2
5m.Contains("ushers")  // true
6m.Nodes()             // 10, one per distinct pattern prefix plus the root

Searching for k patterns by running a single-pattern scan k times costs O(k*n): every extra word in the dictionary is another full pass over the text. Aho-Corasick builds one automaton from the whole set, a trie of the patterns plus a failure link on every node pointing at the longest proper suffix that is also a prefix of some pattern, and then reads the text once. Building the trie and the links costs O(total pattern length), scanning costs O(n + matches), and k does not appear in either.

The text cursor never moves backwards, and that is why it belongs on chain. The worst case equals the best case, so a dictionary and a text chosen by an attacker cost what a friendly pair costs. A naive k-pass scan is one input away from quadratic, and on chain a pathological input is an attack rather than bad luck. It is p/moul/x/daily/kmp generalised: KMP's failure table is this automaton for a one-pattern set.

Four behaviours worth knowing before you use it:

• Every match is reported, including overlapping and nested ones. FindAll is ordered by end offset, and at one end offset the longest match comes first, because the scan reports the node it reached before the shorter suffixes hanging off its failure chain. A caller taking the first match at each end offset gets the greedy one, and a caller wanting only non-overlapping matches filters on Start >= lastEnd itself.
• Match.Index is the caller's slot, not a node number, so a match maps back to whatever was stored alongside the pattern. A duplicated pattern is two slots and reports twice: deduplicating here would silently drop the second caller's payload.
• It matches bytes, not runes. gno strings are UTF-8 and an offset is a byte offset, which is the right unit for slicing. UTF-8 is self-synchronizing, so a pattern that is itself valid UTF-8 can only match on a rune boundary of valid UTF-8 text. The flip side is real: a pattern that is a bare continuation byte does match inside a rune, and slicing there splits it.
• The build is bounded and a refusal is nil. MaxPatterns is 256 and MaxPatternLen is 256, so an on-chain caller cannot be handed an automaton whose size it did not choose. Empty patterns are dropped, since the empty string matches at every offset and that is a different question. A nil matcher answers every method, so the result of New can go straight into a scan without a check.

Each node stores the patterns matching there, merged from its failure target at build time, rather than a link to be walked at every offset. That is a departure from the paper and it is a trade: a reported match costs O(1) instead of a walk up the failure chain, and the build pays memory in exactly one shape, a set whose patterns nest (a, aa, aaa, and so on), where the merged lists are quadratic in the number of patterns rather than linear. MaxPatterns is what bounds that, and nothing else does. A dictionary of distinct words is nowhere near it: the lists are one entry per node.

Node lookup is a binary search over the edges a node actually has, kept sorted by label, rather than a 256-entry row per node. A dictionary of words touches a few dozen distinct bytes, and paying 1 KiB a node for the rest of the alphabet is how this structure gets expensive in the one place a realm cannot afford it.

Live demo: r/moul/x/daily/ahocorasickdemo · render it at /r/moul/x/daily/ahocorasickdemo/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.