nx_kmp_search.nx
buildroot/runtime/nx_kmp_search.nx
about
nx_kmp_search.nx -- Knuth-Morris-Pratt string search.
Worst-case O(n+m) string search via the failure function.
Companion to nx_boyer_moore: KMP gives guaranteed linear worst case;
BM is faster on average for long patterns but worst-case O(n*m).
genealogy_id: knuth_morris_pratt_1977_sicomp
lineage_id: single_pattern_exact_string_search
references: Knuth, Morris, Pratt SICOMP 6(2):323-350, 1977.
CLRS chapter 32.4.
license: public_domain (1977 academic publication)
complexity: O(n+m) time, O(m) space.
dependencies 2 imports · 2 importers
imports: nx_syscalls.nxnx_tier.nx
imported by: nx_kmp_search_test.nxnx_triangulation_sort_string_graph.nx
structs
| none |
consts
| none |
functions
| 26 | func nx_kmp_build_failure(pattern: *u8, m: nx_size, f: *nx_idx) -> nx_int called by 1: nx_kmp_search |
| 51 | func nx_kmp_search(text: *u8, n: nx_size, pattern: *u8, m: nx_size) -> nx_idx |