KMP

Algorithm algorithm

Created At : 2019-08-01 16:47

KMP

王道方法

1) next 数组从1开始

2) next[1] = 0
next[2] = 1
next[0]不使用

3) 求当next数组当前位置j
// 主要方法就是 将前一个位置(j-1)的字符与next[j-1]所对应的字符比较相同则 next[j] = next[j-1]+1;
// 不同则 将next[j-1]的字符 与next[ next[j-1] ]对应否字符相比较相同则 next[j] = next[ next[j-1] ]+1;
// 不断重复
// 如果next[...] = 0 ==> next[j] = 1;
    k = next[j-1]; 
    while(1)
    {
        if(S[k] == S[j-1])//S为字符数组
        {
            next[j] = k+1;
            break;
        }
        else
            k = next[k];
    }
殷人昆

可以直接看前n个串中的最大前缀等于后缀的个数即为 next[j]的值

常见方法
1) next[1]=0

2) 从第j(j>1)个开启比较前j个的最大前缀等于后缀

转换技巧[快速做选择题]

http://www.cskaoyan.com/thread-650235-1-1.html
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

规则1：用常见方法做出结果

规则2：右移一位，最左边添-1，最右边自然溢出

规则3：全部加1