1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
use super::TextProcessing;
use smallvec::SmallVec;
pub trait KMP {
fn kmp_search(&self, pattern: &str) -> SmallVec<[usize; 256]>;
fn kmp_table(graphemes: &[&str]) -> SmallVec<[i32; 256]> {
let mut ret: SmallVec<_> = SmallVec::with_capacity(graphemes.len() + 1);
if graphemes.is_empty() {
return ret;
}
ret.push(-1);
for _ in 0..graphemes.len() {
ret.push(0);
}
let mut pos: usize = 1;
let mut cnd: i32 = 0;
while pos < graphemes.len() {
if graphemes[pos] == graphemes[cnd as usize] {
ret[pos] = ret[cnd as usize];
} else {
ret[pos] = cnd;
cnd = ret[cnd as usize];
while cnd >= 0 && graphemes[pos] != graphemes[cnd as usize] {
cnd = ret[cnd as usize];
}
}
pos += 1;
cnd += 1;
}
ret[pos] = cnd;
ret
}
}
impl KMP for str {
fn kmp_search(&self, pattern: &str) -> SmallVec<[usize; 256]> {
let w = pattern.split_graphemes();
let t = Self::kmp_table(&w);
let mut j = 0;
let mut k = 0;
let mut ret = SmallVec::new();
let s = self.graphemes_indices();
while j < s.len() && k < w.len() as i32 {
if w[k as usize] == s[j].1 {
j += 1;
k += 1;
if k as usize == w.len() {
ret.push(s[j - (k as usize)].0);
k = t[k as usize];
}
} else {
k = t[k as usize];
if k < 0 {
j += 1;
k += 1;
}
}
}
ret
}
}
#[test]
fn test_search() {
use super::_ALICE_CHAPTER_1;
for ind in _ALICE_CHAPTER_1.kmp_search("Alice") {
println!(
"{:#?}",
&_ALICE_CHAPTER_1
[ind.saturating_sub(0)..std::cmp::min(_ALICE_CHAPTER_1.len(), ind + 25)]
);
}
}