KMP

// 获取KMP的前缀表
// 前缀：不包含最后一个字符的字符串列表
//      'aabaaf': ['a','aa','aab','aaba','aabaa']
// 后缀：不包含第一个字符的字符串列表
//      'aabaaf': ['f','af','aaf','baaf','abaaf']
// 前缀表：一个字符串前缀和后缀相等的个数数组
//      'aabaaf': [0,1,0,1,2,0]
//{
// 'a':前缀[],后缀[] -> 前后缀相等个数：0
// 'aa':前缀['a'],后缀['a'] -> 前后缀相等个数：1
// 'aab':前缀['a','aa'],后缀['b','ab'] -> 前后缀相等个数：0
// ...
// }
function getNext(s){
    // j代表前缀最后一个字符的下标 以及 相同前缀后缀的个数
    let j=0;
    // 初始化前缀表，一个字母的前缀和后缀都为0，所以next[0] = 0
    const next = [0];
    // i代表后缀最后一个字符的下标
    for(let i=1;i<s.length;i++){
        // 遇到前缀和后缀最后一个字符不相同时，前缀最后一个字符需要回退
        // 回退到前缀最后一个字符在前缀表中的值
        // 回退之后如果还不相等需要一直后退，直到j===0
        while(j>0 && s[j] !== s[i]){
            j = next[j-1];
        }
        // 如果前缀和后缀最后一个字符相同时，前缀向后移
        if(s[j] === s[i]) j++;
        // 更新前缀表
        next[i] = j;
    }
    return next;
}

console.log(getNext('aabaaf'));

// 获取KMP的前缀表
// 前缀：不包含最后一个字符的字符串列表
//      'aabaaf': ['a','aa','aab','aaba','aabaa']
// 后缀：不包含第一个字符的字符串列表
//      'aabaaf': ['f','af','aaf','baaf','abaaf']
// 前缀表：一个字符串前缀和后缀相等的个数数组
//      'aabaaf': [0,1,0,1,2,0]
//{
// 'a':前缀[],后缀[] -> 前后缀相等个数：0
// 'aa':前缀['a'],后缀['a'] -> 前后缀相等个数：1
// 'aab':前缀['a','aa'],后缀['b','ab'] -> 前后缀相等个数：0
// ...
// }
function getNext(s){
    // j代表前缀最后一个字符的下标 以及 相同前缀后缀的个数
    let j=0;
    // 初始化前缀表，一个字母的前缀和后缀都为0，所以next[0] = 0
    const next = [0];
    // i代表后缀最后一个字符的下标
    for(let i=1;i<s.length;i++){
        // 遇到前缀和后缀最后一个字符不相同时，前缀最后一个字符需要回退
        // 回退到前缀最后一个字符在前缀表中的值
        // 回退之后如果还不相等需要一直后退，直到j===0
        while(j>0 && s[j] !== s[i]){
            j = next[j-1];
        }
        // 如果前缀和后缀最后一个字符相同时，前缀向后移
        if(s[j] === s[i]) j++;
        // 更新前缀表
        next[i] = j;
    }
    return next;
}

console.log(getNext('aabaaf'));

KMP ​

KMP