KMP算法模板&&扩展

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

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

问题描述：

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

 1 const int maxn = 1e6 + 10;
 2 int Next[maxn];
 3 void Getnext(char* p)//next数组初始化
 4 {
 5     int plen = strlen(p);
 6     Next[0] = -1;
 7     int k = -1, j = 0;
 8     while(j < plen - 1)//next优化            j < plen也可以，只是多求了next[plen]
 9     {
10         //p[k]表示前缀  p[j]表示后缀
11         if(k == -1 || p[j] == p[k])
12         {
13             j++, k++;
14             if(p[j] != p[k])Next[j] = k;
15             else Next[j] = Next[k];
16         }
17         else k = Next[k];
18     }
19     /*while(j < plen - 1)//next数组未优化
20     {
21         //p[k]表示前缀  p[j]表示后缀
22         if(k == -1 || p[j] == p[k])
23         {
24             j++, k++;
25             Next[j] = k;
26         }
27         else k = Next[k];
28     }*/
29 }
30 int ans;
31 void KMP(char* s, char* p)//s为文本串，p为匹配串
32 {
33     Getnext(p);ans = 0;//ans为匹配次数
34     int i = 0, j = 0;
35     int slen = strlen(s), plen = strlen(p);
36     while(i < slen)
37     {
38         if(j == -1 || s[i] == p[j])
39             i++, j++;
40         else j = Next[j];
41         if(j == plen)//已经匹配
42         {
43             ans++;
44             //cout<<i - j<<endl;//匹配的下标    从0开始
45             j = next[j];
46             i--;//如果所匹配的子串之间不可相交,去掉i--;
47         }
48     }
49 }

KMP另一版本：感觉更快

 1 int Next[maxn];
 2 void Getnext(char p[], int plen)//next数组初始化
 3 {
 4     Next[1] = 0;
 5     int k = 0;
 6     for(int i = 1; i < plen; i++)
 7     {
 8         while(k > 0 && p[k] != p[i])k = Next[k];
 9         if(p[k] == p[i])k++;
10         Next[i + 1] = k;
11     }
12 }
13 int KMP(char s[], char p[], int slen, int plen)//s为文本串，p为匹配串
14 {
15     Getnext(p, plen);//如果匹配串p一直不变，可以在函数外面调用一次即可
16     int k = 0;
17     int ans = 0;
18     for(int i = 0; i < slen; i++)
19     {
20         while(k > 0 && p[k] != s[i])k = Next[k];
21         if(p[k] == s[i])k++;
22         if(k == plen)
23         {
24             ans++;
25             k = Next[k];//匹配的下标i-j 从0开始
26         }
27     }
28     return ans;
29 }

KMP算法扩展：

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

 1 //扩展KMP算法
 2 //求字符串S的后缀 与字符串T的最长公共前缀长度
 3 //extand[i]表示S[i...slen] 与 T的最长公共前缀长度
 4 //Next[i]表示T[i...tlen] 与 T的最长公共前缀长度 也就是最长公共前后缀长度
 5 
 6 char s[maxn], t[maxn];
 7 int Next[maxn], extand[maxn];
 8 void Getnext(char t[])//预处理出Next数组
 9 {
10     int tlen = strlen(t), i = 0;
11     Next[0] = tlen;//从0开始的后缀（就是T） 和 T的公共前缀就是T本身
12     while(i < tlen - 1 && t[i] == t[i + 1])i++;
13     Next[1] = i;
14     int a = 1;
15     for(int i = 2; i < tlen; i++)
16     {
17         int p = a + Next[a] - 1, L = Next[i - a];//p为当前匹配到的最远位置，a表示从a开始匹配可以匹配到这个最大位置
18         if(i - 1 + L >= p)//情况2
19         {
20             int j = (p - i + 1) > 0 ? (p - i + 1) : 0;
21             while(i + j < tlen && t[i + j] == t[j])j++;
22             Next[i] = j;
23             a = i;
24         }
25         else Next[i] = L;//情况1
26     }
27 }
28 void Getextand(char* s, char* t)
29 {
30     memset(Next, 0, sizeof(Next));
31     Getnext(t);
32     int slen = strlen(s), tlen = strlen(t);
33     int Minlen = Min(slen, tlen);
34     int a = 0;
35     while(a < Minlen && s[a] == t[a])a++;
36     extand[0] = a;
37     a = 0;
38     for(int i = 1; i < slen; i++)
39     {
40         int p = a + extand[a] - 1, L = Next[i - a];
41         if(i - 1 + L >= p)//情况2
42         {
43             int j = (p - i + 1) > 0 ? (p - i + 1) : 0;
44             while(i + j < slen && j < tlen && s[i + j] == t[j])j++;
45             extand[i] = j;
46             a = i;
47         }
48         else extand[i] = L;
49     }
50 }