KMP算法模板&&扩展

很不错的学习链接：https://blog.****.net/v_july_v/article/details/7041827

具体思路就看上面的链接就行了，这里只放几个常用的模板

问题描述：

给出字符串a和b，求a中匹配b的所有下标

 const int maxn = 1e6 + ;
 int Next[maxn];
 void Getnext(char* p)//next数组初始化
 {
     int plen = strlen(p);
     Next[] = -;
     int k = -, j = ;
     while(j < plen - )//next优化            j < plen也可以，只是多求了next[plen]
     {
         //p[k]表示前缀  p[j]表示后缀
         if(k == - || p[j] == p[k])
         {
             j++, k++;
             if(p[j] != p[k])Next[j] = k;
             else Next[j] = Next[k];
         }
         else k = Next[k];
     }
     /*while(j < plen - 1)//next数组未优化
     {
         //p[k]表示前缀  p[j]表示后缀
         if(k == -1 || p[j] == p[k])
         {
             j++, k++;
             Next[j] = k;
         }
         else k = Next[k];
     }*/
 }
 int ans;
 void KMP(char* s, char* p)//s为文本串，p为匹配串
 {
     Getnext(p);ans = 0;//ans为匹配次数
     int i = , j = ;
     int slen = strlen(s), plen = strlen(p);
     while(i < slen)
     {
         if(j == - || s[i] == p[j])
             i++, j++;
         else j = Next[j];
         if(j == plen)//已经匹配
         {
             ans++;
             //cout<<i - j<<endl;//匹配的下标    从0开始
             j = next[j];
             i--;//如果所匹配的子串之间不可相交,去掉i--;
         }
     }
 }

KMP另一版本：感觉更快

 int Next[maxn];
 void Getnext(char p[], int plen)//next数组初始化
 {
     Next[] = ;
     int k = ;
     for(int i = ; i < plen; i++)
     {
         while(k >  && p[k] != p[i])k = Next[k];
         if(p[k] == p[i])k++;
         Next[i + ] = k;
     }
 }
 int KMP(char s[], char p[], int slen, int plen)//s为文本串，p为匹配串
 {
     Getnext(p, plen);//如果匹配串p一直不变，可以在函数外面调用一次即可
     int k = ;
     int ans = ;
     for(int i = ; i < slen; i++)
     {
         while(k >  && p[k] != s[i])k = Next[k];
         if(p[k] == s[i])k++;
         if(k == plen)
         {
             ans++;
             k = Next[k];//匹配的下标i-j 从0开始
         }
     }
     return ans;
 }

KMP算法扩展：

https://wenku.baidu.com/view/8e9ebefb0242a8956bece4b3.html?from=search

 //扩展KMP算法
 //求字符串S的后缀 与字符串T的最长公共前缀长度
 //extand[i]表示S[i...slen] 与 T的最长公共前缀长度
 //Next[i]表示T[i...tlen] 与 T的最长公共前缀长度 也就是最长公共前后缀长度

 char s[maxn], t[maxn];
 int Next[maxn], extand[maxn];
 void Getnext(char t[])//预处理出Next数组
 {
     int tlen = strlen(t), i = ;
     Next[] = tlen;//从0开始的后缀（就是T） 和 T的公共前缀就是T本身
     while(i < tlen -  && t[i] == t[i + ])i++;
     Next[] = i;
     int a = ;
     for(int i = ; i < tlen; i++)
     {
         int p = a + Next[a] - , L = Next[i - a];//p为当前匹配到的最远位置，a表示从a开始匹配可以匹配到这个最大位置
         if(i -  + L >= p)//情况2
         {
             int j = (p - i + ) >  ? (p - i + ) : ;
             while(i + j < tlen && t[i + j] == t[j])j++;
             Next[i] = j;
             a = i;
         }
         else Next[i] = L;//情况1
     }
 }
 void Getextand(char* s, char* t)
 {
     memset(Next, , sizeof(Next));
     Getnext(t);
     int slen = strlen(s), tlen = strlen(t);
     int Minlen = Min(slen, tlen);
     int a = ;
     while(a < Minlen && s[a] == t[a])a++;
     extand[] = a;
     a = ;
     for(int i = ; i < slen; i++)
     {
         int p = a + extand[a] - , L = Next[i - a];
         if(i -  + L >= p)//情况2
         {
             int j = (p - i + ) >  ? (p - i + ) : ;
             while(i + j < slen && j < tlen && s[i + j] == t[j])j++;
             extand[i] = j;
             a = i;
         }
         else extand[i] = L;
     }
 }