KMP算法

理解kmp算法
如何去理解k = next[k]

手撕代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int getNext(int []next,string s){
    int k = -1, j = 0;
    next[0] = -1;
    while(j < s.size()){
        if(k == -1 || s[j] == s[k]){
            j++;
            k++;
            if(s[j] == s[k]){  
                next[j] = next[k];
            }else{
                next[j] = k;
            }
        }eles{
            k = next[k];  //如何去理解这个呢
        }
    }
}

如何理解k = next[k]?


按照我的想法应该是这样的

  • k = next[k] 其实就是一种回退，如果没有找到相应的前缀，使得在s[i]~s[j]之间的字符串，字符串的前缀和后缀是否有相同之处，然后再赋值给next数组

    这个照片讲的比之前很详细，如果是按照上图这张解释，就可以理解为什么 k = next[k];