| 52 | |
| 53 | impl From<&str> for KMP { |
| 54 | fn from(pat: &str) -> Self { |
| 55 | let R = 256; |
| 56 | let M = pat.len(); |
| 57 | |
| 58 | // build DFA from pattern |
| 59 | let mut dfa = vec![vec![0; M]; R]; |
| 60 | dfa[byte_at(pat, 0)][0] = 1; |
| 61 | let mut x = 0; |
| 62 | for j in 1..M { |
| 63 | // Compute dfa[][j]. |
| 64 | for c in 0..R { |
| 65 | dfa[c][j] = dfa[c][x]; // Copy mismatch cases. |
| 66 | } |
| 67 | // for match case, DFA step to j + 1 |
| 68 | dfa[byte_at(pat, j)][j] = j + 1; // Set match case. |
| 69 | x = dfa[byte_at(pat, j)][x]; // Update restart state. |
| 70 | } |
| 71 | |
| 72 | Self { M, dfa } |
| 73 | } |
| 74 | } |