kmp.gno

 1// Package kmp implements Knuth–Morris–Pratt substring search as a pure,
 2// reusable package.
 3//
 4// The naive scan re-compares characters it has already matched, so a hostile
 5// input like "aaaaaaab" in "aaaaaaaaaaaaaaab" costs O(n*m). KMP precomputes a
 6// failure table — for every prefix, the length of the longest proper prefix
 7// that is also a suffix — and uses it to slide the pattern without ever moving
 8// the text cursor backwards. That makes the scan O(n+m) with O(m) extra memory,
 9// and it never degrades: worst case equals best case, which is what makes it
10// safe to run on chain where a pathological input is an attack, not bad luck.
11//
12// Operates on BYTES, not runes: gno strings are UTF-8, so a match index is a
13// byte offset. That is the right unit for slicing and it keeps the failure
14// table cheap; callers doing rune arithmetic must convert.
15//
16// A live demo of this package is at
17// [r/moul/x/daily/kmpdemo](/r/moul/x/daily/kmpdemo/v0).
18package kmp
19
20// MaxPattern bounds the failure table so gas stays predictable.
21const MaxPattern = 1024
22
23// Table returns the KMP failure table for pattern: table[i] is the length of
24// the longest proper prefix of pattern[:i+1] that is also a suffix of it.
25// Returns nil when the pattern is empty or longer than MaxPattern.
26func Table(pattern string) []int {
27	m := len(pattern)
28	if m == 0 || m > MaxPattern {
29		return nil
30	}
31	t := make([]int, m)
32	k := 0
33	for i := 1; i < m; i++ {
34		for k > 0 && pattern[i] != pattern[k] {
35			k = t[k-1]
36		}
37		if pattern[i] == pattern[k] {
38			k++
39		}
40		t[i] = k
41	}
42	return t
43}
44
45// Index returns the byte offset of the first occurrence of pattern in text, or
46// -1 if absent. An empty pattern matches at 0, matching strings.Index.
47func Index(text, pattern string) int {
48	all := findAll(text, pattern, 1)
49	if len(all) == 0 {
50		return -1
51	}
52	return all[0]
53}
54
55// Contains reports whether pattern occurs in text.
56func Contains(text, pattern string) bool { return Index(text, pattern) >= 0 }
57
58// FindAll returns the byte offsets of every match, including OVERLAPPING ones:
59// FindAll("aaaa", "aa") is [0 1 2], not [0 2]. Overlap is the honest reading of
60// "every occurrence" and the caller can always filter.
61func FindAll(text, pattern string) []int { return findAll(text, pattern, 0) }
62
63// Count returns how many times pattern occurs, counting overlaps.
64func Count(text, pattern string) int { return len(FindAll(text, pattern)) }
65
66// findAll collects match offsets, stopping after limit matches (0 = no limit).
67func findAll(text, pattern string, limit int) []int {
68	m := len(pattern)
69	if m == 0 {
70		return []int{0}
71	}
72	if m > len(text) || m > MaxPattern {
73		return nil
74	}
75	t := Table(pattern)
76	if t == nil {
77		return nil
78	}
79
80	var out []int
81	k := 0
82	for i := 0; i < len(text); i++ {
83		for k > 0 && text[i] != pattern[k] {
84			k = t[k-1]
85		}
86		if text[i] == pattern[k] {
87			k++
88		}
89		if k == m {
90			out = append(out, i-m+1)
91			if limit > 0 && len(out) >= limit {
92				return out
93			}
94			k = t[k-1] // allow overlapping matches
95		}
96	}
97	return out
98}