nx_rabin_karp.nx
buildroot/runtime/nx_rabin_karp.nx
about
nx_rabin_karp.nx -- string search via rolling polynomial hash.
genealogy_id: karp_rabin_1987_rolling_hash
lineage_id: single_pattern_exact_string_search
references: Karp & Rabin 1987 IBM J. R&D; CLRS 32.2.
license: public_domain
complexity: expected O(n+m), worst O(nm) on adversarial input.
dependencies 2 imports · 2 importers
imports: nx_syscalls.nxnx_tier.nx
imported by: nx_rabin_karp_test.nxnx_triangulation_sort_string_graph.nx
structs
| none |
consts
| 18 | const NX_RK_BASE: nx_int = 257 |
| 19 | const NX_RK_MOD: nx_int = 1000000007 |
functions
| 23 | func nx_rabin_karp(text: *u8, n: nx_size, pattern: *u8, m: nx_size) -> nx_idx |