nx_rabin_karp.nx source
↩ module page · 72 lines · 2389 B
1// nx_rabin_karp.nx -- string search via rolling polynomial hash.
2//
3// genealogy_id: karp_rabin_1987_rolling_hash
4// lineage_id: single_pattern_exact_string_search
5// references: Karp & Rabin 1987 IBM J. R&D; CLRS 32.2.
6// license: public_domain
7// complexity: expected O(n+m), worst O(nm) on adversarial input.
8
9// nx_safety_envelope:
10// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
11// sil_target: SIL1
12// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
13// verdict: NOT_YET_EVALUATED
14
15import "nx_syscalls.nx"
16import "nx_tier.nx"
17
18const NX_RK_BASE: nx_int = 257
19const NX_RK_MOD: nx_int = 1000000007
20
21// Find first occurrence of pattern (length m) in text (length n).
22// Returns byte index or -1.
23func nx_rabin_karp(text: *u8, n: nx_size, pattern: *u8, m: nx_size) -> nx_idx {
24 if m == 0 { return 0 }
25 if m > n { return -1 }
26
27 // Precompute BASE^(m-1) mod MOD.
28 var h: nx_int = 1
29 var i: nx_idx = 0
30 while i < m - 1 {
31 h = (h * NX_RK_BASE) - ((h * NX_RK_BASE) / NX_RK_MOD) * NX_RK_MOD
32 i = i + 1
33 }
34
35 // Hash of pattern + first window.
36 var p_hash: nx_int = 0
37 var t_hash: nx_int = 0
38 var j: nx_idx = 0
39 while j < m {
40 p_hash = (p_hash * NX_RK_BASE + pattern[j] as nx_int)
41 p_hash = p_hash - (p_hash / NX_RK_MOD) * NX_RK_MOD
42 t_hash = (t_hash * NX_RK_BASE + text[j] as nx_int)
43 t_hash = t_hash - (t_hash / NX_RK_MOD) * NX_RK_MOD
44 j = j + 1
45 }
46
47 var k: nx_idx = 0
48 let last: nx_idx = n - m
49 while k <= last {
50 if p_hash == t_hash {
51 // Verify byte-by-byte (avoid false positives).
52 var l: nx_idx = 0
53 var ok: nx_int = 1
54 while l < m {
55 if text[k + l] != pattern[l] { ok = 0; l = m }
56 if ok == 1 { l = l + 1 }
57 }
58 if ok == 1 { return k }
59 }
60 if k < last {
61 // Slide the window: subtract leading char, add trailing.
62 var th: nx_int = (t_hash - (text[k] as nx_int) * h) * NX_RK_BASE
63 th = th + (text[k + m] as nx_int)
64 // Normalize mod (may be negative after subtraction).
65 th = th - (th / NX_RK_MOD) * NX_RK_MOD
66 if th < 0 { th = th + NX_RK_MOD }
67 t_hash = th
68 }
69 k = k + 1
70 }
71 return -1
72}