1.求出T（模板串）对S（原串）的最小完全匹配位置 HDU-1711 Number Sequence (普通kmp)
2.求T（模板串）在S（原串）中出现的次数(可以重复匹配) POJ-3461 Oulipo （kmp修改）
3.求T（模板串）在S（原串）出现的次数（不可重复匹配）HDU-2087 剪花布条
4.求字符串S的最小的循环节 HDU-3746 Cyclic Nacklace ，HDU-1358 Period (KMP循环节问题) ，POJ-2406 Power Strings
5.找到（输出）字符串S中所有的 公共前后缀 部分 POJ-2752 Seek the Name, Seek the Fame （KMP）
5*.输出 字符串S中所有的 公共前后缀串之和 HDU-3336 Count the string (KMP)
6.找出所给的多个串的相同子串部分 POJ-3080 Blue Jeans (KMP优化匹配)
7.给出两个字符串a,b然后求a前缀与b后缀的最长公共部分 并输出 长度 HDU-2594 Simpsons’ Hidden Talents (kmp) 也可以说是 （扩展kmp）
模板总结：
求某个字符串的next数组 (对于kmp而言)
const int maxn = 1e5+7;int nex[maxn];char str[maxn]; void getnext(char *str){ int i=0,j=-1; int len = strlen(str); nex[i]=j; while(i<len){ if(j==-1||str[i]==str[j]){ i++;j++; nex[i]=j; } else j=nex[j]; } }
KMP 求最小位置匹配,以及否出现判断（没有出现输出返回-1）:
int nex[maxn]; char str[maxn];//文本串 char str1[maxn];//模式串 int kmp(){ int i = 0, j = 0; getnext(str1); int len = strlen(str); int len1 = strlen(str1); while(i < len && j < len1) { if(j == -1 || a[i] == b[j]) { i++; j++; } else j = nex[j]; } return (j==len1)?(i -len1 + 1):-1; }
KMP 求匹配次数
int nex[maxn]; char str[maxn];//文本串 char str1[maxn];//模式串 int kmp(char *str, char *str1){ int ans = 0; int i = 0,j = 0; int len,len1; len = strlen(str),len1 = strlen(str1); if(len == 1 && len1 == 1){ return (str[0] == str1[0]) ? 1 : 0; } getnext(str1); for(i=0;i<len;i++){ while( j>0 && str[i]!=str1[j] ){ j=nex[j]; } if(str[i] == str1[j]) j++; if(j==len1){ ans++; j=nex[j];//重复统计次数 //j = 0；不重复统计次数 } } return ans; }
KMP 求循环节个数（如果不存在则返回-1）
int loop(char *str){ int len = strlen(str); //nex[len] == 0时必然没有循环节 if(nex[len]!=0){ //循环节长度 int k = len - nex[len]; //如果循环节个数不为0 if(!(len % k)){ //求出循环节个数 int num = len / k; return num; } } else return -1; }
计算某个字符串的所有前缀子串，在字符串出现的次数的总和
例如 s: "abab"
The prefixes are: "a", "ab", "aba", "abab"
The sum = 2 + 2 + 1 + 1 = 6.
//(1)求所有前缀和 int len = strlen(str);//母串for(int i=1;i<=len;i++){ dp[i]=dp[nex[i]]+1; sum = (sum+dp[i])%mod; }//(2)回溯 找到所有公共的前缀部分ans = nex[nex[i]];
求扩展KMP的 extend[]数组：
//str2为模板串,str1为原串（母串）void getnext(char *str2){ nex[0]=len2; int j=0,p; while(j+1<len1&&str2[j]==str2[j+1])j++; nex[1]=j; int k=1; for(int i=2;i<len2;i++){ p=nex[k]+k-1; if(i+nex[i-k]-1<p) nex[i]=nex[i-k]; else{ j = max(0,p-i+1); while(i+j<len2&&str2[i+j]==str2[j])j++; nex[i]=j; k=i; } } } void exkmp(char *str1,char *str2){ getnext(); int j=0,p; int len = min(len1,len2); while(j<len&&str2[j]==str1[j])j++; extend[0]=j; int k=0; for(int i=1;i<len1;i++){ p = extend[k]+k-1; if(i+nex[i-k]-1<p) extend[i]=nex[i-k]; else{ j=max(0,p-i+1); while(i+j<len1&&j<len1&&str1[i+j]==str2[j])j++; extend[i]=j; k=i; } } }
转载于:https://www.cnblogs.com/Tianwell/p/11249345.html
相关资源：JAVA上百实例源码以及开源项目