题目大意:对于一个字符串,找由循环字符串组成的位置,并输出最多循环了几次,比如两个样例,第一个是 aaa ,所以在第二个位置由子串a循环两次得到,第三个位置由a循环3次,第二个样例aabaabaabaab,在第二个位置由a循环两次,在第六个位置由aab循环两次,在第9个位置由aab循环3次,在第12个位置由aab循环4次,注意,在第12个位置不是由aabaab循环2次,因为要求循环次数最多。
kmp可以解决循环子串问题,kmp中首先预处理出来一个p数组,p[ i ]=a表示前a个字符等于后a个字符,仔细想一下,前面a个字符往后平移i-a字符后与后面a个字符重合,令i - a = L,所以a[ 1 ] = a[ 1+ L],因为a[ 1+ L]也往后平移了,所以a[ 1+ L] = a[ 1+ 2*L]=a[ 1+ 3*L]=......,所以说如果a[ i ] 是循环子串的话i必须能整除L,循环次数为i/L,画个图会帮助理解~~
#include <stdio.h>
char a[1000020];
int p[1000020];
int main()
{
int n,i,j,tot=1;
while(1)
{
scanf("%d",&n);
if(n==0) break;
getchar();
for(i=1;i<=n;i++) scanf("%c",&a[i]);
j=0;
p[1]=0;
for(i=2;i<=n;i++)
{
while(j>0&&a[i]!=a[j+1]) j=p[j];
if(a[i]==a[j+1])
j++;
p[i]=j;
}
printf("Test case #%d\n",tot);
for(i=1;i<=n;i++)
if(p[i]!=0&&i%(i-p[i])==0)
printf("%d %d\n",i,i/(i-p[i]));
printf("\n");
tot++;
}
return 0;
}
转载于:https://www.cnblogs.com/vermouth/p/3710194.html
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)