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

v0 source pure

Package kmp implements Knuth–Morris–Pratt substring search as a pure, reusable package.

Readme View source

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.

Overview

Package kmp implements Knuth–Morris–Pratt substring search as a pure, reusable package.

The naive scan re-compares characters it has already matched, so a hostile input like "aaaaaaab" in "aaaaaaaaaaaaaaab" costs O(n*m). KMP precomputes a failure table — for every prefix, the length of the longest proper prefix that is also a suffix — and uses it to slide the pattern without ever moving the text cursor backwards. That makes the scan O(n+m) with O(m) extra memory, and it never degrades: worst case equals best case, which is what makes it safe to run on chain where a pathological input is an attack, not bad luck.

Operates on BYTES, not runes: gno strings are UTF-8, so a match index is a byte offset. That is the right unit for slicing and it keeps the failure table cheap; callers doing rune arithmetic must convert.

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

Constants 1

const MaxPattern 

1const MaxPattern = 1024
source

MaxPattern bounds the failure table so gas stays predictable.

Functions 5

func Contains 

1func Contains(text, pattern string) bool
source

Contains reports whether pattern occurs in text.

func Count 

1func Count(text, pattern string) int
source

Count returns how many times pattern occurs, counting overlaps.

func FindAll 

1func FindAll(text, pattern string) []int
source

FindAll returns the byte offsets of every match, including OVERLAPPING ones: FindAll("aaaa", "aa") is [0 1 2], not [0 2]. Overlap is the honest reading of "every occurrence" and the caller can always filter.

func Index 

1func Index(text, pattern string) int
source

Index returns the byte offset of the first occurrence of pattern in text, or -1 if absent. An empty pattern matches at 0, matching strings.Index.

func Table 

1func Table(pattern string) []int
source

Table returns the KMP failure table for pattern: table[i] is the length of the longest proper prefix of pattern[:i+1] that is also a suffix of it. Returns nil when the pattern is empty or longer than MaxPattern.

Source Files 3