gno.land/p/moul/x/daily/kmp/v0⧉

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 hostile5// input like "aaaaaaab" in "aaaaaaaaaaaaaaab" costs O(n*m). KMP precomputes a6// failure table — for every prefix, the length of the longest proper prefix7// that is also a suffix — and uses it to slide the pattern without ever moving8// 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 it10// 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 a13// byte offset. That is the right unit for slicing and it keeps the failure14// table cheap; callers doing rune arithmetic must convert.15//16// A live demo of this package is at17// [r/moul/x/daily/kmpdemo](/r/moul/x/daily/kmpdemo/v0).18package kmp1920// MaxPattern bounds the failure table so gas stays predictable.21const MaxPattern = 10242223// Table returns the KMP failure table for pattern: table[i] is the length of24// 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 nil30	}31	t := make([]int, m)32	k := 033	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] = k41	}42	return t43}4445// Index returns the byte offset of the first occurrence of pattern in text, or46// -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 -151	}52	return all[0]53}5455// Contains reports whether pattern occurs in text.56func Contains(text, pattern string) bool { return Index(text, pattern) >= 0 }5758// 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 of60// "every occurrence" and the caller can always filter.61func FindAll(text, pattern string) []int { return findAll(text, pattern, 0) }6263// Count returns how many times pattern occurs, counting overlaps.64func Count(text, pattern string) int { return len(FindAll(text, pattern)) }6566// 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 nil74	}75	t := Table(pattern)76	if t == nil {77		return nil78	}7980	var out []int81	k := 082	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 out93			}94			k = t[k-1] // allow overlapping matches95		}96	}97	return out98}99