昨天把KMP复习了一下,顺便做了一些以前做过的题,貌似有那么点感觉O(∩_∩)O~
贴出来,方便以后复习,O(∩_∩)O~
http://poj.org/problem
View Code #include<stdio.h>
#include<string.h>
const int N = 1000000+10;
char str[N];
int next[N];
int len;
void GetNext1(char str[N],int next[N])//寻找模式串的粗略next
{
int l=strlen(str);
next[0]=-1;
int i=0,j=-1;
while(i<l)
{
if(j==-1||str[i]==str[j])
{
i++;j++;
next[i]=j;
}
else
j=next[j];
}
}
int main()
{
int T = 0;
while(scanf("%d",&len)!=EOF)
{
T++;
if(len == 0)break;
scanf("%s",str);
GetNext1(str,next);
int i;
printf("Test case #%d\n",T);
for(i=2;i<=len;i++)
{
if(next[i]!=0&&i%(i-next[i])==0)//保证不是原串且循环
{
printf("%d %d\n",i,i/(i-next[i]));
}
}
printf("\n");
}
return 0;
}
http://poj.org/problem?id=2406
POJ 2406 Power Strings
大意:给出一个字符串S,求该字符串最多是由相同重复字串连接而成的
若S由n个A组成,则称 S = A^n,求最大的n
如 S=aaa,S="a"^3 => n = 3;
S=ababa => n = 1
分析:KMP
与POJ 1961类似,而且更简单:
若L%(L-next[L])==0,n = L/(L-next[L]),else n = 1
View Code #include<stdio.h>
#include<string.h>
const int N = 1000000+10;
char str[N];
int next[N];
int len;
void GetNext1(char str[N],int next[N])//寻找模式串的粗略next
{
int l=strlen(str);
next[0]=-1;
int i=0,j=-1;
while(i<l)
{
if(j==-1||str[i]==str[j])
{
i++;j++;
next[i]=j;
}
else
j=next[j];
}
}
int main()
{
int T = 0;
while(scanf("%s",str)!=EOF)
{
if(strcmp(str,".")==0)break;
GetNext1(str,next);
int len = strlen(str);
if(len%(len-next[len])==0)
printf("%d\n",len/(len-next[len]));
else
printf("1\n");
}
return 0;
}
http://poj.org/problem
View Code #include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
vector<int>ans;
const int N = 1000000+10;
char str[N];
int next[N];
void GetNext1(char str[N],int next[N])//寻找模式串的粗略next
{
int l=strlen(str);
next[0]=-1;
int i=0,j=-1;
while(i<l)
{
if(j==-1||str[i]==str[j])
{
i++;j++;
next[i]=j;
}
else
j=next[j];
}
}
int main()
{
while(scanf("%d",&str)!=EOF)
{
scanf("%s",str);
GetNext1(str,next);
int cur,len;
len = strlen(str);
cur = len;
ans.clear();
while(cur)
{
ans.push_back(cur);
cur = next[cur];
}
if(str[0]==str[len])//首位字符相同
ans.push_back(1);
int sz = ans.size();
for(cur = sz-1;cur>0;cur--)
printf("%d ",ans[cur]);
printf("%d\n",ans[0]);
}
return 0;
}