algorithms_fourth 0.1.10

//! 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);
//!
//! ```
//! 
//! # 原理
//! <pre>
//! 用二维数组(dfa)存储当字符c在位置j时匹配模式字符串(txt)的最大长度。<br>
//! 行号为字符在编码中的位置，列号为字符在模式字符串中的位置。<br>
//! 初始状态:第一列除了dfa[txt[0]][0] = 1 外，其他一定为0。<br> 
//! 推导：
//!     第二列除了dfa[txt[1]][1] = 2 = dfa[txt[0]][0] = 1 + 1 外，
//! 其他位置的c因为一定不匹配txt[1]所以实际上是需要从头匹配，也就是dfa[c][0]对应的信息。<br>
//!     第三列除了dfa[txt[2]][2]]= 3 = dfa[txt[1]][1] + 1 外，
//! 其他位置的c因为一定不匹配txt[2],
//! 所以实际上需要知道txt[1..=2]的后缀 与txt[0..=1]的前缀的最大交集，
//! 所以结果是dfa[][0] 、dfa[][1]中的一个，这里是个if逻辑，所以需要分析跳转逻辑。<br>
//!         当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列时对应的匹配长度
//!</pre> 
//! 

use crate::generate_vec_with;

const R: usize = 256;
pub struct KMP {
    pat: String,
    /// 二维数组，每个位置表示当字符c出现在位置j时的匹配长度
    /// （同时也是下一个字符要匹配模式字符串的位置）
    dfa: Vec<Vec<usize>>,
}
fn char_at(s: &str, d: usize) -> usize {
    s.as_bytes()[d] as usize
}
impl KMP {
    pub fn new(pat: String) -> Self {
        let m = pat.len();
        let mut dfa = generate_vec_with!(vec![0; m], R);
        // 第0个字符在0位置上对应的匹配长度是1
        dfa[char_at(&pat, 0)][0] = 1;
        // x 记录当前位置字符匹配失败时的可匹配模式的最大长度。
        // 第0个位置的除第0个字符外一定是0，所需无需修改
        let mut x = 0;
        // 整个过程是个推导过程，知道起始值，知道规律，则知道将来
        for j in 1..m {
            // 一个位置只会有一个字符匹配成为最长字符
            // ，其他字符一定是回退到x长度时的匹配情况。
            // 所以，这里直接拷贝x长度时对应字符的匹配长度
            (0..R).for_each(|c| {
                dfa[c][j] = dfa[c][x];
            });
            // 最长匹配串对应的字符行
            let i = char_at(&pat, j);
            // 第j个字符在j位置上对应的匹配长度是j+ 1
            dfa[i][j] = j + 1;
            // x怎么变是关键，
            // 根据前边的定义，x列记录字符在匹配失败时的可匹配模式的最大长度，
            // 所以它存的就是下一个x的值
            x = dfa[i][x];
        }

        KMP { pat, dfa }
    }
    /// 成功返回匹配的开始位置，
    ///
    /// 失败返回文本的长度
    pub fn search(&self, txt: &str) -> usize {
        let n = txt.len();
        let m = self.pat.len();
        let mut j = 0;
        let i: Vec<usize> = (0..n)
            .filter(|&i| {
                j = self.dfa[char_at(txt, i)][j];
                j >= m
            })
            .take(1)
            .collect();
        if j == m {
            if let Some(i) = i.first() {
                i + 1 - m
            } else {
                n - m
            }
        } else {
            n
        }
    }
}
#[cfg(test)]
mod test {
    use super::KMP;

    #[test]
    fn test() {
        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);
    }
}