算法情景分析 Kmp 的next数组

刚刚看到有网友在问Kmp next数组，
心宗有若干想法，就在这儿写下来吧，

任何算法有了实现，才有生命，code就是生命的载体啊。
但是优秀的算法，code总是那么精炼。
kmp也是，不能不贴上代码。
来一段吧：

void SetPrefix(const char *Pattern, int prefix[])



{

     int len=CharLen(Pattern);//模式字符串长度。

     prefix[0]=0;

     for(int i=1; i<len; i++)

     {

         int k=prefix[i-1];

         //不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推

         while( Pattern[i] != Pattern[k]  &&  k!=0 )               

             k=prefix[k-1];  



         if( Pattern[i] == Pattern[k])//找到了这个子对称，或者是直接继承了前面的对称性，这两种都在前面的基础上++

              prefix[i]=k+1;



         else

              prefix[i]=0;       //如果遍历了所有子对称都无效，说明这个新字符不具有对称性，清0

     }



copyright @yearn520

首先说作用吧：
kmp的next数组是用来表征自我 覆盖程度，值越小，覆盖程度越低。

那么如何表示自我覆盖程度

3个列子：
前提：next元素初始值为-1
再给前面的代码给个标示：
while( Pattern[i] != Pattern[k] && k!=0 ) k=prefix[k-1]; //情形1
//特别注明：如果next数组（即prefix数组）初始值为-1，这里纠正0为-1

if( Pattern[i] == Pattern[k]) prefix[i]=k+1; //情形2
prefix[i]=0; //情形3，特别注明：如果next数组（即prefix数组）初始值为-1，这里纠正0为-1


case 1: aaaa
aaaa对应的next数组：next[]={-1,0,1,2};
计算过程对应代码路径：一直只执行 情形2 ,lucky!!

case 2: abcd
aaaa对应的next数组：next[]={-1 -1 -1 -1};
计算过程对应代码路径：一直只执行 情形3 ,bad luck!

case 3: ababab
aaaa对应的next数组：next[]={-1 -1 0 1 2 3};
计算过程对应代码路径：先后执行 情形 3,情形3，然后 情形一直情形2

为什么要kmp

这是一个学习kmp算法反复要问自己的话题，
当前我认为就是用空间换时间，用next提供的信息来告诉匹配过程少走弯路。


下一次有时间结合使用Next数组的程序讲解。

初次学习，不免疏漏，请大家指教。