再次学习kmp

大学学数据结构的时候学的KMP，看了两个星期代码，就是有空就看看代码，琢磨琢磨明白了。没有看教材上的解析是因为那个解析太生涩了！

KMP的难点在于next数组的求解过程

next[i]存储的是什么，存储的next[0 ~ i-1]这个字符串后缀与前缀最大的相同长度(设为value_l)
这样当在 b[i]匹配失败的时候，转到下标value_l处继续匹配 //b[value_l] 和 b[i]不相同，但是它们前面长度value_l的字符串却相同。
如何快速求出next数组呢？
先初始化一下
　　next[0] = -1; //b[0]匹配失败的时候直接后移，重新开始。不为-1就是移动b，而不是调整b的位置
　　int i = 1; 　　 //要求解的next[i] 的 i
　　int j = 0; //这是一个游标，表示next[0,i-1]前后缀最大的公共长度
如果b[i] == b[j]
　　那么已经知道b[i]如果匹配失败转移到哪里去了，转移到next[j];因为最后一个字符相同导致现在是j+1个字符相同，转到j同样也会失败.
　　//所以说这句代码可以这么些 next[i] = next[j];
　　i和j 都皆大欢喜，携手往前一步 i++, j++; //公共长度+1 再接再厉求下一个结果
如果不相同呢
　　那么已经知道b[i]如果匹配失败转移到哪里去了，转移到下标j
　　//下次要计算next[i+1]的，它的最大前后缀公共长度j肯定需要调整的，我们就在这里收拾这个烂摊子
　　j, next[j], next[next[j]], next[next[next[j]]], …, 0 j这样依次往前跳，这些点的共同特征是什么
　　所有有可能和next[0~i]的后缀相同的前缀都在这里了!!! 说的是b[0, j]们
　　　　其实也不是都在这里，但是所有合适的前缀的都在这个列表里
　　　　即使有漏网之鱼，i和j协同前进的步伐肯定碾压过它们，但是它们为什么被忽略了呢？//说的就是 next[i] = next[j] 里面的 j 不会出现在这个枚举列表里
　　　　关键点就在于它们的最后一个字符必须要和b[i]对上，但是和它最后相同的但是更长的都在枚举列表里面，如果那个都没被选上，那么这个j直接被忽略就太合理了
　　所以调整j的位置就是枚举呀
　　然后j都为求next[i+1]调整好了,i也就可以往前走一步了

void cal_next(char* b, int* next, int length)
{
    int i = 1;
    int j = 0;
    next[0] = -1;
    while(i<length)
    {
        if(b[i] == b[j]){
            next[i] = next[j];
            i++, j++;
        }else{
            next[i] = j;
            //找到相同的公共部分为了next[i+1]的计算
            while(j != -1 && b[j] != b[i])
                j = next[j];
            if( b[i] == b[j] )
                i++, j++;
            else
                i++;
        }
    }
}

记得在数据结构里面有代码形式更简洁妖艳的写法，我个人对那段代码是极度拜服。。但是那段形式上最简化的代码(所有while跑的次数没有优化)，并且却不便与这样理解。贴网上的不保证正确

void get_next(string b, int *next)
{
    int i=0;
    int j=-1;
    next[i]=-1;
    int len_b=b.size();
    while(i<len_b-1)
    {
        if(j==-1||b[i]==b[j])
        {
            ++i;
            ++j;
            if(b[i]!=b[j])
                next[i]=j;
            else
                next[i]=next[j];
        }
        else
        {
            j = next[j];
        }
    }
}

KMP的难点在于next数组的求解过程

目录