kmpdemo.gno

 1// Package kmpdemo is a small gnoweb demo of the Knuth–Morris–Pratt substring
 2// 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 is
 6// deterministic — which is precisely what the library is for.
 7package kmpdemo
 8
 9import (
10	"strconv"
11	"strings"
12
13	"gno.land/p/moul/x/daily/kmp/v0"
14)
15
16// Render renders the demo for gnoweb.
17func Render(path string) string {
18	var b strings.Builder
19	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")
22
23	const text = "mississippi"
24	const pattern = "issi"
25
26	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	}
34
35	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")
45
46	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")
51
52	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}
59
60func 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}