nx_kmp_search.nx source
↩ module page · 79 lines · 2537 B
1// nx_kmp_search.nx -- Knuth-Morris-Pratt string search.
2//
3// Worst-case O(n+m) string search via the failure function.
4// Companion to nx_boyer_moore: KMP gives guaranteed linear worst case;
5// BM is faster on average for long patterns but worst-case O(n*m).
6//
7// genealogy_id: knuth_morris_pratt_1977_sicomp
8// lineage_id: single_pattern_exact_string_search
9// references: Knuth, Morris, Pratt SICOMP 6(2):323-350, 1977.
10// CLRS chapter 32.4.
11// license: public_domain (1977 academic publication)
12// complexity: O(n+m) time, O(m) space.
13
14// nx_safety_envelope:
15// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
16// sil_target: SIL1
17// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
18// verdict: NOT_YET_EVALUATED
19
20import "nx_syscalls.nx"
21import "nx_tier.nx"
22
23// Build the failure-function table f[i] = length of the longest proper
24// prefix of pattern[0..i] that is also a suffix. Used to advance the
25// pattern cursor without re-examining text characters.
26func nx_kmp_build_failure(pattern: *u8, m: nx_size, f: *nx_idx) -> nx_int {
27 f[0] = 0
28 var k: nx_int = 0
29 var i: nx_idx = 1
30 while i < m {
31 var done: nx_int = 0
32 while done == 0 {
33 if k > 0 {
34 if pattern[k] != pattern[i] {
35 k = f[k - 1]
36 } else {
37 done = 1
38 }
39 } else {
40 done = 1
41 }
42 }
43 if pattern[k] == pattern[i] { k = k + 1 }
44 f[i] = k
45 i = i + 1
46 }
47 return 0
48}
49
50// Search pattern (length m) inside text (length n). Returns index or -1.
51func nx_kmp_search(text: *u8, n: nx_size, pattern: *u8, m: nx_size) -> nx_idx {
52 if m == 0 { return 0 }
53 if m > n { return -1 }
54
55 let f_raw: *u8 = sys_mmap(m * 8)
56 let f: *nx_idx = f_raw as *nx_idx
57 nx_kmp_build_failure(pattern, m, f)
58
59 var q: nx_int = 0 // pattern cursor
60 var i: nx_idx = 0 // text cursor
61 while i < n {
62 var advanced: nx_int = 0
63 while advanced == 0 {
64 if q > 0 {
65 if pattern[q] != text[i] {
66 q = f[q - 1]
67 } else {
68 advanced = 1
69 }
70 } else {
71 advanced = 1
72 }
73 }
74 if pattern[q] == text[i] { q = q + 1 }
75 if q == m { return i - m + 1 }
76 i = i + 1
77 }
78 return -1
79}