KMP中next数组的懂得

KMP中next数组的理解

对于KMP算法中的next数组大家估计都不是很陌生。

但是，next数组的意义好像是一知半解。不过next数组的博大精深，令我小辈唏嘘。

一般的next求解：

void Get_Next(){
    next[0]=-1;
    int j=-1,i=0;
    while(i<len){
        if(j==-1||str[j]==str[i]){
            j++;i++;
            next[i]=j;
        }
        else j=next[j];
    }
}

代码很是简单。

我们知道，在运行KMP算法的时候，模式串和主串失配的时候，主串不动（失配位置为i），我们就可以将模式串的失配位置j，移到next[j]位置，继续进行匹配。从而减少了很多的不必要的匹配。

那么next数组的具体意义在什么地方呢？那么为什么当失配的时候可以将模式串的位置移到next[j]呢？

我们知道，可以移到next[j]，是因为，模式串中从第一个字符到低next[j]个字符和从第j-next[j]到第j和字符是一样的。看下图：

KMP中next数组的懂得

其实到这里，我们是可以看出来的，next[i]数组的实际意义就是前i个字符前缀和后缀的最大匹配数。

那么我们可以用这个数组来作什么呢？？？

第一，求字串中【前缀+跟前缀相同的子串】的个数，详细看这篇文字：点击打开链接

第二，求一个字符串的最短周期。

我们知道，根据next数组的理解，next[i]就是指前i个字符串中，前缀和后缀的最大匹配数。

那么我们可以得到结论，i-next[i]就是前i个字符的最短周期。

为什么？？对，凡事不懂，要问为什么。

几个例子：

KMP中next数组的懂得

推荐做几道题目：Hdu3746 Cyclic Nacklace点击打开链接

Hdu1358 Period 点击打开链接都是又换周期的问题。

好了KMP就先了解到这里，接下来要弄AC自动机了。

4楼u012492762昨天 09:59: 你好，刚好前几天在搞KMP，今天也准备搞AC自动机，有时间一块交流，交流吧！新博客地址，上面有我对KMP算法的理解！http://www.cnblogs.com/scottding/p/3603527.html

3楼u012492762昨天 09:44: 昨天安鹏程和我说，你在HDU上开了一个专题，我本来是准备搜你的专题的，结果把你的博客给搜出来了！

2楼u012492762昨天 09:41: 你应该是南阳理工的张开创吧！昨天好像看到你在那看AC自动机了，我师院的，昨天去你们小黑屋找安鹏程的那个!

1楼u012492762昨天 09:31: 有空多交流AC自动机啊！

相关推荐