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.

v0 source pure

Package ahocorasick implements Aho-Corasick multi-pattern search as a pure, reusable package.

Readme View source

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.

Overview

Package ahocorasick implements Aho-Corasick multi-pattern search as a pure, reusable package.

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 failure links costs O(total pattern length) and scanning costs O(n + matches), whatever k is, and the text cursor never moves backwards.

One deliberate departure from the paper: each node stores the full list of patterns matching there, merged from its failure target at build time, rather than a link to be walked at every offset. That makes a reported match O(1) instead of a walk up the failure chain, and it costs build memory in exactly one shape, a set whose patterns nest ("a", "aa", "aaa", ...), where the merged lists are quadratic in k rather than linear. MaxPatterns is what bounds that, and nothing else does.

That last property is why it is worth having on chain: the worst case equals the best case, so a dictionary and a text chosen by an attacker cost the same as a friendly pair. A naive k-pass scan is an input away from quadratic.

It is p/moul/x/daily/kmp(/p/moul/x/daily/kmp/v0) generalised: KMP's failure table is this automaton for a one-pattern set.

Operates on BYTES, not runes. gno strings are UTF-8 and a match 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; a pattern that is a bare continuation byte can and will match inside a rune, and slicing on that offset splits it.

A live demo of this package is at r/moul/x/daily/ahocorasickdemo(/r/moul/x/daily/ahocorasickdemo/v0).

Constants 1

const MaxPatterns, MaxPatternLen 

1const (
2	MaxPatterns   = 256
3	MaxPatternLen = 256
4)
source

Bounds on what New will build, so an on-chain caller cannot be handed an automaton whose size it did not choose. At most MaxPatterns*MaxPatternLen+1 nodes exist, and the build is linear in the total pattern length.

Functions 1

func New 

1func New(patterns []string) *Matcher
source

New builds the automaton for patterns. Empty patterns are dropped: the empty string matches at every offset, which is a different question from the one this package answers.

Returns nil when there is nothing to build (no pattern survives the drop) or when the set exceeds the bounds above. A nil Matcher answers every method, so a caller may hand the result straight to a scan without a check.

Types 2

type Match

struct 
1type Match struct {
2	Start   int
3	End     int
4	Index   int
5	Pattern string
6}
source

Match is one occurrence of one pattern. Start and End are byte offsets into the text, half-open, so text[Start:End] is the matched run. Index is the pattern's slot in the slice given to New, which is how a caller maps a match back to whatever it stored alongside the pattern.

type Matcher

struct 
1type Matcher struct {
2	patterns []string
3	nodes    []node
4}
source

Matcher is a built automaton. It is immutable once New returns, so one Matcher can serve any number of scans.

Methods on Matcher

func Contains

method on Matcher 
1func (m *Matcher) Contains(text string) bool
source

Contains reports whether any pattern occurs in text.

func FindAll

method on Matcher 
1func (m *Matcher) FindAll(text string) []Match
source

FindAll returns every occurrence of every pattern, including overlapping and nested ones, ordered by end offset. 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, so a caller taking the first match at each offset gets the greedy one.

func FindFirst

method on Matcher 
1func (m *Matcher) FindFirst(text string) (Match, bool)
source

FindFirst returns the first match FindAll would return, and stops the scan there. The one to reach for when the question is "does this text contain anything from the list, and where".

func Nodes

method on Matcher 
1func (m *Matcher) Nodes() int
source

Nodes returns the size of the automaton: one node per distinct pattern prefix, plus the root. The number a caller sizing a dictionary wants, since it is what the build actually costs.

func Patterns

method on Matcher 
1func (m *Matcher) Patterns() []string
source

Patterns returns the accepted patterns, in the caller's order, as a copy.

Dependencies

Imports 0

Imports nothing.

/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/ahocorasick/v0

Imported by indexer

Find the packages that import it

Source Files 4