学步园

题意：给定一字符串T，T=A1*A2*A3...An，且A1=A2=...An，求n的最大值。

思路：利用next[]函数的关系求解。

ps:初涉KMP，还不是很了解，不多说，春节回来，再深入理解下。

#include<stdio.h><br /> #include<string.h><br /> #define maxn 1000008<br /> char T[maxn];<br /> int next[maxn];<br /> void getnext(char s[],int next[]) {<br /> next[0] = -1;<br /> int j = -1;<br /> int len1=strlen(s);<br /> for (int i = 1; i < len1; ++i) {<br /> while (j > -1 && s[j+1] != s[i])<br /> j = next[j];<br /> if (s[j+1] == s[i])<br /> ++j;<br /> next[i] = j;<br /> }<br /> }<br /> int main()<br /> {<br /> char a[2]=".";<br /> while(scanf("%s",&T)!=EOF)<br /> {<br /> if(strcmp(a,T)==0)<br /> break;<br /> getnext(T,next);<br /> int n=strlen(T);<br /> if(n%(n-next[n-1]-1)==0)<br /> printf("%d/n",n/(n-next[n-1]-1));<br /> else printf("%d/n",1);<br /> }<br /> return 0;<br /> }

另一种求next[]函数的写法(更高效，也更严谨，但不易理解)：

#include<stdio.h><br /> #include<string.h><br /> #define maxn 1000008<br /> char T[maxn];<br /> int next[maxn];<br /> void getnext(char T[],int next[])<br /> {<br /> int n=strlen(T),i,j;<br /> next[0]=-1;i=0;j=-1;<br /> while(i<n)<br /> {<br /> if(j==-1||T[i]==T[j])<br /> {<br /> ++i;++j;<br /> if(T[i]!=T[j]) next[i]=j;<br /> else next[i]=next[j];//此处注意<br /> }<br /> else j=next[j];<br /> }<br /> /*for(i=0;i<n;i++)<br /> printf("%d ",next[i]);<br /> printf("/n");*/<br /> }<br /> int main()<br /> {<br /> char a[2]=".";<br /> while(scanf("%s",&T)!=EOF)<br /> {<br /> if(strcmp(a,T)==0)<br /> break;<br /> getnext(T,next);<br /> int n=strlen(T);<br /> if(n%(n-next[n])==0)<br /> printf("%d/n",n/(n-next[n]));<br /> else printf("%d/n",1);<br /> }<br /> return 0;<br /> }