Algorithm_字符匹配算法

KMP算法

主要的关键点在于NEXT数组————最长公共前后缀

寻找前后缀的方法：

• 找前缀时，要找除了最后一个字符的所有子串
• 找后缀时，要找除了第一个字符的所有子串

void Getnext(int next[],String t)
{
   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
   {
      if(k == -1 || t[j] == t[k])
      {
         j++;k++;
         next[j] = k;//next[j] = k，表示当T[i] != P[j]时，j指针的下一个位置
      }
      else k = next[k];
   }
}

当P[k] == P[j]时，

有next[j+1] == next[j] + 1