KMP经典习题

KMP 算法经典题目：

pku2406 Power Strings

http://162.105.81.212/JudgeOnline/problem?id=2406

pku1961 Period

http://162.105.81.212/JudgeOnline/problem?id=1961

 这个题目是1961的升级版，考察队next数组的应用，附上代码：

#include <iostream> #include <stdio.h> #include <string.h> using namespace std; const int ma=1e6+5; char s[ma]; int nex[ma]; void Pre_next(int len) { int i=0,j=-1; nex[0]=-1; while(i<len) { while(j!=-1&&s[i]!=s[j]) j=nex[j]; nex[++i]=++j; } } int main() { int cas=1,len; while(scanf("%d",&len)&&len) { scanf("%s",s); printf("Test case #%d\n",cas++); Pre_next(len); int res; for(int i=2; i<=len; ++i) { res=1; if(i%(i-nex[i])==0) res=i/(i-nex[i]); if(res>1) printf("%d %d\n",i,res); } printf("\n"); } return 0; }

pku2752 Seek the Name, Seek the Fame

http://162.105.81.212/JudgeOnline/problem?id=2752

 

pku3461 Oulipo

http://162.105.81.212/JudgeOnline/problem?id=3461

 

pku2185 Milking Grid

http://162.105.81.212/JudgeOnline/problem?id=2185

 

zjut1349 掷硬币

http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1349

 

几道非常经典的KMP题目，很巧的利用了kmp中pre数组（前缀数组）的特性。

留题号备忘，附get_next和匹配模板。

void Get_next(int len) //目标串的长度 { int i=0,j=-1; nex[0]=-1; while(i<len) { while(j!=-1&&s[i]!=s[j]) j=nex[j]; nex[++i]=++j; } }

int KMP_Count(int m,int n) //m:模式串长度,n:待匹配串长度 { int i,j,ans=0; i=j=0; Get_nex(m); //计算next[]数组 while(i<n) { while(j!=-1&&y[i]!=x[j]) j=nex[j]; ++i;++j; if(j>=m) { ans++; j=nex[j]; } } return ans; }