gno.land/r/moul/x/daily/kmpdemo/v0⧉

1// Package kmpdemo is a small gnoweb demo of the Knuth–Morris–Pratt substring2// search provided by the [p/moul/x/daily/kmp](/p/moul/x/daily/kmp/v0) library:3// it shows the failure table and overlapping matches.4//5// It contains no search logic of its own. Stateless, so Render is6// deterministic — which is precisely what the library is for.7package kmpdemo89import (10	"strconv"11	"strings"1213	"gno.land/p/moul/x/daily/kmp/v0"14)1516// Render renders the demo for gnoweb.17func Render(path string) string {18	var b strings.Builder19	b.WriteString("# Knuth–Morris–Pratt\n\n")20	b.WriteString("Linear-time substring search, demoing the ")21	b.WriteString("[`p/moul/x/daily/kmp`](/p/moul/x/daily/kmp/v0) library.\n\n")2223	const text = "mississippi"24	const pattern = "issi"2526	b.WriteString("## Failure table\n\n")27	b.WriteString("For each prefix of `" + pattern + "`, the length of the longest proper ")28	b.WriteString("prefix that is also a suffix. This is what lets the scan slide the ")29	b.WriteString("pattern without ever rewinding the text.\n\n")30	b.WriteString("| i | prefix | table |\n|---|---|---|\n")31	for i, v := range kmp.Table(pattern) {32		b.WriteString("| " + strconv.Itoa(i) + " | `" + pattern[:i+1] + "` | " + strconv.Itoa(v) + " |\n")33	}3435	b.WriteString("\n## Searching\n\n")36	b.WriteString("`" + pattern + "` in `" + text + "`:\n\n")37	b.WriteString("```\n" + text + "\n")38	hits := kmp.FindAll(text, pattern)39	for _, at := range hits {40		b.WriteString(strings.Repeat(" ", at) + strings.Repeat("^", len(pattern)) + "\n")41	}42	b.WriteString("```\n\n")43	b.WriteString("Matches at " + offsets(hits) + " — **overlapping**, and `Count` agrees: ")44	b.WriteString(strconv.Itoa(kmp.Count(text, pattern)) + ".\n\n")4546	b.WriteString("## Overlap is deliberate\n\n")47	b.WriteString("`FindAll(\"aaaa\", \"aa\")` returns " + offsets(kmp.FindAll("aaaa", "aa")))48	b.WriteString(", not just the disjoint ones — \"every occurrence\" read honestly. ")49	b.WriteString("A caller wanting disjoint matches can filter; one wanting overlap ")50	b.WriteString("could not recover it.\n\n")5152	b.WriteString("## Why it belongs on chain\n\n")53	b.WriteString("The naive scan is O(n·m): `")54	b.WriteString(strings.Repeat("a", 8) + "b` inside `" + strings.Repeat("a", 16))55	b.WriteString("b` re-compares everything it already matched. KMP is O(n+m) with no ")56	b.WriteString("bad case, so a pathological input is not an attack.\n")57	return b.String()58}5960func offsets(xs []int) string {61	if len(xs) == 0 {62		return "_none_"63	}64	parts := make([]string, len(xs))65	for i, x := range xs {66		parts[i] = "`" + strconv.Itoa(x) + "`"67	}68	return strings.Join(parts, ", ")69}70