render_example_test.gno

 1package kmpdemo
 2
 3// ExampleRender pins the realm's Render output as a testable example.
 4func ExampleRender() {
 5	print(Render(""))
 6	// Output:
 7	// # Knuth–Morris–Pratt
 8	//
 9	// Linear-time substring search, demoing the [`p/moul/x/daily/kmp`](/p/moul/x/daily/kmp/v0) library.
10	//
11	// ## Failure table
12	//
13	// For each prefix of `issi`, the length of the longest proper prefix that is also a suffix. This is what lets the scan slide the pattern without ever rewinding the text.
14	//
15	// | i | prefix | table |
16	// |---|---|---|
17	// | 0 | `i` | 0 |
18	// | 1 | `is` | 0 |
19	// | 2 | `iss` | 0 |
20	// | 3 | `issi` | 1 |
21	//
22	// ## Searching
23	//
24	// `issi` in `mississippi`:
25	//
26	// ```
27	// mississippi
28	//  ^^^^
29	//     ^^^^
30	// ```
31	//
32	// Matches at `1`, `4` — **overlapping**, and `Count` agrees: 2.
33	//
34	// ## Overlap is deliberate
35	//
36	// `FindAll("aaaa", "aa")` returns `0`, `1`, `2`, not just the disjoint ones — "every occurrence" read honestly. A caller wanting disjoint matches can filter; one wanting overlap could not recover it.
37	//
38	// ## Why it belongs on chain
39	//
40	// The naive scan is O(n·m): `aaaaaaaab` inside `aaaaaaaaaaaaaaaab` re-compares everything it already matched. KMP is O(n+m) with no bad case, so a pathological input is not an attack.
41}