学步园

问题描述：寻找一个字符串中的某个子串，它是由某个字符串"连续重复构成"，求出“连续重复次数最多”构成的那个sub—字符串。如果存在多个结果，求出字典排序最小的一个。

比如对于字符串abababcc，“ababab”是最大连续重复子串，其中“ab”重复次数是3。

再比如：bbbaaa，问题的答案是“aaa”，”a“重复3次构成。虽然"bbb"也是由"b"连续三次构成，但是字典排序"aaa"<"bbb"。

问题求解：

这个问题可以把”连续重复字符串“看作一个子问题（参看之前blog），然后遍历整个字符串的长度L，对每个长度为L的子串都调用”子问题“，分别求出每个子串的next数组，最后取重复次数最多的结果（如果唯一，否则，字典排序子串）。

这样的时间复杂度很高，但是实在也想不出什么高效的算法，杯具……

#include <iostream><br /> #include <cstdlib><br /> #include <cstdio><br /> #include <cstring><br /> using namespace std;<br /> int next[100010];<br /> char s[100010];<br /> char max_s[100010];<br /> int max_times;<br /> void get_next(int n,char *s)<br /> {<br /> int i=0;<br /> next[i]=-1;<br /> int j=next[0];<br /> while(i<=n)<br /> {<br /> if(j==-1 || s[i]==s[j])<br /> {<br /> i++;<br /> j++;<br /> next[i]=j;<br /> }<br /> else<br /> j = next[j];<br /> }<br /> }<br /> void solve(int st,int en)<br /> {<br /> memset(next,0,sizeof(next));<br /> int len = en-st+1;<br /> get_next(len,s+st);<br /> int t = len - next[len];<br /> int times = 1;<br /> if(len%t==0)<br /> {<br /> times = len/t;<br /> }<br /> else<br /> times=1;<br /> if(max_times == len/t)<br /> {<br /> char *tmp_s = new char[t+1];<br /> memset(tmp_s,0,sizeof(tmp_s));<br /> strncpy(tmp_s,s+en+1-t,t);<br /> if(strcmp(max_s,tmp_s)>0)<br /> {<br /> memset(max_s,0,sizeof(max_s));<br /> strncpy(max_s,s+en+1-t,t);<br /> }<br /> delete []tmp_s;<br /> }<br /> if(max_times<times)<br /> {<br /> max_times = times;<br /> memset(max_s,0,sizeof(max_s));<br /> strncpy(max_s,s+en+1-t,t);<br /> }<br /> }<br /> int main()<br /> {<br /> scanf("%s",s);<br /> int c=1;<br /> while(s[0]!='#')<br /> {<br /> int i,j;<br /> int l = strlen(s);<br /> for(i=0;i<l;i++)<br /> for(j=i;j<l;j++)<br /> {<br /> if(j-i+1<max_times)<br /> continue;<br /> solve(i,j);<br /> }<br /> printf("Case %d:",c);<br /> for(i=0;i<max_times;i++)<br /> printf("%s",max_s);<br /> cout<<endl;<br /> memset(s,0,sizeof(s));<br /> memset(next,0,sizeof(next));<br /> memset(max_s,0,sizeof(max_s));<br /> max_times=0;<br /> c++;<br /> scanf("%s",s);<br /> }<br /> }<br />