KMP算法(Knuth Morris Pratt)

1. pub fn knuth_morris_pratt(st: String, pat: String) -> Vec<usize> {
2. if st.is_empty() || pat.is_empty() {
3. return vec![];
4. }

6. let string = st.into_bytes();
7. let pattern = pat.into_bytes();

9. // build the partial match table
10. let mut partial = vec![0];
11. for i in 1..pattern.len() {
12. let mut j = partial[i - 1];
13. while j > 0 && pattern[j] != pattern[i] {
14. j = partial[j - 1];
15. }
16. partial.push(if pattern[j] == pattern[i] { j + 1 } else { j });
17. }

19. // and read 'string' to find 'pattern'
20. let mut ret = vec![];
21. let mut j = 0;

23. for (i, &c) in string.iter().enumerate() {
24. while j > 0 && c != pattern[j] {
25. j = partial[j - 1];
26. }
27. if c == pattern[j] {
28. j += 1;
29. }
30. if j == pattern.len() {
31. ret.push(i + 1 - j);
32. j = partial[j - 1];
33. }
34. }

36. ret
37. }

39. #[cfg(test)]
40. mod tests {
41. use super::*;

43. #[test]
44. fn each_letter_matches() {
45. let index = knuth_morris_pratt("aaa".to_string(), "a".to_string());
46. assert_eq!(index, vec![0, 1, 2]);
47. }

49. #[test]
50. fn a_few_separate_matches() {
51. let index = knuth_morris_pratt("abababa".to_string(), "ab".to_string());
52. assert_eq!(index, vec![0, 2, 4]);
53. }

55. #[test]
56. fn one_match() {
57. let index =
58. knuth_morris_pratt("ABC ABCDAB ABCDABCDABDE".to_string(), "ABCDABD".to_string());
59. assert_eq!(index, vec![15]);
60. }

62. #[test]
63. fn lots_of_matches() {
64. let index = knuth_morris_pratt("aaabaabaaaaa".to_string(), "aa".to_string());
65. assert_eq!(index, vec![0, 1, 4, 7, 8, 9, 10]);
66. }

68. #[test]
69. fn lots_of_intricate_matches() {
70. let index = knuth_morris_pratt("ababababa".to_string(), "aba".to_string());
71. assert_eq!(index, vec![0, 2, 4, 6]);
72. }

74. #[test]
75. fn not_found0() {
76. let index = knuth_morris_pratt("abcde".to_string(), "f".to_string());
77. assert_eq!(index, vec![]);
78. }

80. #[test]
81. fn not_found1() {
82. let index = knuth_morris_pratt("abcde".to_string(), "ac".to_string());
83. assert_eq!(index, vec![]);
84. }

86. #[test]
87. fn not_found2() {
88. let index = knuth_morris_pratt("ababab".to_string(), "bababa".to_string());
89. assert_eq!(index, vec![]);
90. }

92. #[test]
93. fn empty_string() {
94. let index = knuth_morris_pratt("".to_string(), "abcdef".to_string());
95. assert_eq!(index, vec![]);
96. }
97. }