KMP专题
POJ 2406 Power Strings
http://poj.org/problem?id=2406
题意：找出s字符窜由多少个重复子窜循环构成
分析：KMP求出next数组，其i-next[i]就是到i为止前面循环节是多少
那么i/(i-next[i])就是有几个循环节，注意这里的i不是下标，是长度，注意一定要i能够整除(i-next[i])
#include<stdio.h>
#include<string.h>
const int MN=1000010;
int next[MN];
char s[MN];
int len;
void get_next()
{
next[0]=0;
next[1]=0;
for(int i=1;i<len;i++)
{
int j=next[i];
while(j && s[i]!=s[j]) j=next[j];
next[i+1]=s[i]==s[j]?j+1:0;
}
}
int main()
{
int i,j;
while(scanf("%s",s))
{
if(strcmp(s,".")==0) break;
len=strlen(s);
get_next();
if(len%(len-next[len])==0)printf("%d\n",len/(len-next[len]));
else printf("1\n");
}
return 0;
}POJ 3461 Oulipo
http://poj.org/problem?id=3461
题意：s2包含多少个s1
模板题
#include<stdio.h>
#include<string.h>
const int MN=1000010;
int next[MN];
char s1[MN],s2[MN];
int len;
int ans;
void find(char *T,char *P,int *f)
{
ans=0;
int n=strlen(T),m=strlen(P);
int j=0;
for(int i=0;i<n;i++)
{
while(j && P[j]!=T[i]) j=f[j];
if(P[j]==T[i]) j++;
if(j==m) ans++;
}
}
void get_next()
{
int len=strlen(s1);
next[0]=next[1]=0;
for(int i=1;i<len;i++)
{
int j=next[i];
while(j && s1[i]!=s1[j]) j=next[j];
next[i+1]=s1[i]==s1[j]?j+1:0;
}
}
int main()
{
int i,j;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",s1);
scanf("%s",s2);
get_next();
find(s2,s1,next);
printf("%d\n",ans);
}
return 0;
}POJ 2752 Seek the Name, Seek the Fame http://poj.org/problem?id=2752
题意：找出前缀后缀一样的
分析：回溯next数组就是答案
我们可以看next[i]=k,表明第i位置的字符的前k个字符和开始的字符相同，此时i位置和k位置的字符不一定相同 但是i-1和k-1是相同的，当i=len的时候，其len-1就是字符窜的最后一个字符必定和next[len]-1的字符相同的
#include<stdio.h>
#include<string.h>
const int MN= 400010;
char s[MN];
int next[MN];
int num[MN];
void get_next(char *P,int *f)
{
int m=strlen(P);
f[0]=f[1]=0;
for(int i=1;i<m;i++)
{
int j=f[i];
while(j && P[i]!=P[j]) j=f[j];
f[i+1]=P[i]==P[j]?j+1:0;
}
}
int main()
{
int i,j;
while(scanf("%s",s)!=EOF)
{
get_next(s,next);
int len=strlen(s);
int cas=0;
num[cas++]=len;
for(i=len;;)
{
if(next[i]==0) break;
num[cas++]=next[i];
i=next[i];
}
printf("%d",num[cas-1]);
for(i=cas-2;i>=0;i--)
printf(" %d",num[i]);
printf("\n");
}
return 0;
}POJ 2185 Milking Grid
http://poj.org/problem?id=2185
题意：从一个矩阵中找到小矩阵，该子窜小矩阵，其重复能覆盖成大矩阵
分析：将每一行当作一个判断字符来求行的next，然后再求列的next 然后再依据循环节的知识先来判断需要几行，然后再需要求第i行的循环节num[i] 算出最大的子窜长度res，然后判断res%num[i]?=0，若等于0，则说明该最大循环节也是该行的循环节 这是为了避免如， 2 2 ababab ccccccc 其结果是4
数组行列写反了RE到挂.....
#include<stdio.h>
#include<string.h>
const int MR=10010;
const int MC=100;
char s[MR][MC];
int nextC[MR][MC];
int nextR[MR];
int n,m;
int num[MR];
bool judge(int x,int y)
{
if(strcmp(s[x],s[y])==0) return true;
return false;
}
void get_NextR()
{
nextR[0]=nextR[1]=0;
for(int i=1; i<n; i++)
{
int j=nextR[i];
while(j && !judge(i,j)) j=nextR[j];
nextR[i+1]=judge(i,j)?j+1:0;
}
}
void get_NextC()
{
for(int k=0; k<n; k++)
{
nextC[k][0]=nextC[k][1]=0;
for(int i=1; i<m; i++)
{
int j=nextC[k][i];
while(j && s[k][i]!=s[k][j]) j=nextC[k][j];
nextC[k][i+1]=s[k][i]==s[k][j]?j+1:0;
}
}
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0; i<n; i++)
scanf("%s",s[i]);
get_NextR();
get_NextC();
int ans=n-nextR[n];
int res=0;
for(i=0; i<ans; i++)//找最大循环节
{
num[i]=m-nextC[i][m];
if(num[i]>res) res=num[i];
}
for(i=0; i<ans; i++)
{
if(res%num[i]!=0) break;
}
printf("%d\n",ans*res);
}
return 0;
}