Module kmp 

Knuth-Morris-Pratt 字符串查找算法

使用

        use algorithms_fourth::search::kmp::KMP;
        let kmp = KMP::new("abc".to_string());
        assert_eq!(kmp.search("ababac"), 6);
        assert_eq!(kmp.search("ababcc"), 2);
        assert_eq!(kmp.search("ababccababcc"), 2);
        assert_eq!(kmp.search("abcbcc"), 0);
        assert_eq!(kmp.search("babcbcc"), 1);
        assert_eq!(kmp.search("aabcbcc"), 1);
        assert_eq!(kmp.search("ab"), 2);

原理

 用二维数组(dfa)存储当字符c在位置j时匹配模式字符串(txt)的最大长度。

 行号为字符在编码中的位置，列号为字符在模式字符串中的位置。

 初始状态:第一列除了dfa[txt[0]][0] = 1 外，其他一定为0。
 
 推导：
     第二列除了dfa[txt[1]][1] = 2 = dfa[txt[0]][0] = 1 + 1 外，
 其他位置的c因为一定不匹配txt[1]所以实际上是需要从头匹配，也就是dfa[c][0]对应的信息。

     第三列除了dfa[txt[2]][2]]= 3 = dfa[txt[1]][1] + 1 外，
 其他位置的c因为一定不匹配txt[2],
 所以实际上需要知道txt[1..=2]的后缀 与txt[0..=1]的前缀的最大交集，
 所以结果是dfa[][0] 、dfa[][1]中的一个，这里是个if逻辑，所以需要分析跳转逻辑。

         当txt[1] == txt[0] 时，选择dfa[c][1]， 否则，选择dfa[c][0]。
         所以关键的记录txt[1] == txt[0]的信息。而这个信息明显是第二列中当除 c = txt[1]  时记录的信息。
         此外当c = txt[1] 时，dfa[c][1]中记录的信息恰巧是if中的目标j。
        
 发现：
     dfa[][j] 也表示当txt[0..j]为txt的前缀时，字符c在第j列时对应的匹配长度

Structs

KMP