(http://www.elijahqi.win/2017/07/13/【poj2406】/) Power Strings Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 48867 Accepted: 20366 Description
Given two strings a and b we define a*b to be their concatenation. For example, if a = “abc” and b = “def” then a*b = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n). Input
Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case. Output
For each s you should print the largest n such that s = a^n for some string a. Sample Input
abcd aaaa ababab . Sample Output
1 4 3 Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.
据说后缀数组倍增+rmq都超时了，我写完之后发现也超时了，不过证明后缀数组写的还算对，kmp留待填坑
首先构造sa，height等数组 height表示排名第i和排名i-1数组lcp是多少 增设rm数组 rm[排名]=与整个字符串的lcp 判断时，如果i不能被n整除那么也就不可能成为循环节 如果suffix[i+1]可以和整个字符串匹配，且匹配长度正好等于suffix[i+1]那么说明 循环节是n/i;
#include<cstdio> #include<cstring> #define N 1100000 int rank[N<<1],rank1[N],st[N],count[N],tmp[N],sa[N],k,height[N],rm[N]; char a[N]; int main(){ freopen("poj2406.in","r",stdin); freopen("poj2406.out","w",stdout); while (1){ scanf("%s",a+1); if (a[1]=='.') break; memset(st,0,sizeof(st)); memset(rank,0,sizeof(rank)); memset(rank1,0,sizeof(rank1)); int n=strlen(a+1); for (int i=1;i<=n;++i) st[a[i]]=1; for (int i=1;i<=255;++i) st[i]+=st[i-1]; for (int i=1;i<=n;++i) rank[i]=st[a[i]]; k=0; for (int p=1;k!=n;p+=p){ memset(count,0,sizeof(count)); for (int i=1;i<=n;++i) count[rank[i+p]]++; for (int i=1;i<=n;++i) count[i]+=count[i-1]; for (int i=n;i>=1;--i) tmp[count[rank[i+p]]--]=i; memset(count,0,sizeof(count)); for (int i=1;i<=n;++i) count[rank[tmp[i]]]++; for (int i=1;i<=n;++i) count[i]+=count[i-1]; for (int i=n;i>=1;--i) sa[count[rank[tmp[i]]]--]=tmp[i]; memcpy(rank1,rank,sizeof(rank)>>1); rank[sa[1]]=k=1; for (int i=2;i<=n;++i){ if (rank1[sa[i]]!=rank1[sa[i-1]]||rank1[sa[i]+p]!=rank1[sa[i-1]+p]) ++k; rank[sa[i]]=k; } } // for (int i=1;i<=n;++i) printf("%d ",sa[i]);printf("\n"); k=0; for (int i=1;i<=n;++i){ if (rank[i]==1) { height[rank[i]]=0;continue; } k=k==0?0:k-1; while (a[i+k]==a[sa[rank[i]-1]+k])++k; height[rank[i]]=k; } //for (int i=1;i<=n;++i) printf("%d ",height[i]);printf("\n"); k=rank[1]; rm[k]=1000000; for (int i=k-1;i>=0;--i) if (height[i+1]<rm[i+1]) rm[i]=height[i+1];else rm[i]=rm[i+1]; for (int i=k+1;i<=n;++i) if (height[i-1]<rm[i-1]) rm[i]=height[i];else rm[i]=rm[i-1]; //for (int i=1;i<=n;++i) printf("%d ",rm[i]); bool flag=false; for (int i=1;i<=n/2;++i){ if (n%i) continue; if (rm[rank[i+1]]==n-i) { printf("%d\n",n/i);flag=true;break; } } if (flag==false )printf("1\n"); } return 0; }在做kmp之前首先还要复习一下kmp的定义包括求法等
kmp：给定两个字符串如T,S求 S在T 中能否匹配能的话返回匹配的位置
我们首先用一个图来描述kmp算法的思想。在字符串S中寻找T，当匹配到位置i时两个字符串不相等，这时我们需要将字符串T向前移动。常规方法是每次向前移动一位，但是它没有考虑前i-1位已经比较过这个事实，所以效率不高。事实上，如果我们提前计算某些信息，就有可能一次前移多位。假设我们根据已经获得的信息知道可以前移k位，我们分析移位前后的T有什么特点。我们可以得到如下的结论：
A段字符串是T的一个前缀。 B段字符串是T的一个后缀。 A段字符串和B段字符串相等。 所以前移k位之后，可以继续比较位置i的前提是T的前i-1个位置满足：长度为i-k-1的前缀A和后缀B相同。只有这样，我们才可以前移k位后从新的位置继续比较。
图片中 O代表S，f代表T
所以kmp算法的核心即是计算字符串f每一个位置之前的字符串的前缀和后缀公共部分的最大长度（不包括字符串本身，否则最大长度始终是字符串本身）。获得f每一个位置的最大公共长度之后，就可以利用该最大公共长度快速和字符串O比较。当每次比较到两个字符串的字符不同时，我们就可以根据最大公共长度将字符串f向前移动(已匹配长度-最大公共长度)位，接着继续比较下一个位置。事实上，字符串f的前移只是概念上的前移，只要我们在比较的时候从最大公共长度之后比较f和O即可达到字符串f前移的目的。
next数组计算 这个最大公共长度在算法导论里面被记为next数组
在这里要注意一点，next数组表示的是长度，下标从1开始；但是在遍历原字符串时，下标还是从0开始。
在求得next数组后例如 ababab next[6] = 4; 即
ababab ababab 1~4位 与2~6位是相同的
那么前两位 就等于3、4位 3、4位就等于5、6位 …… 所以 如果 能整除 也就循环到最后了
#include<cstdio> #include<cstring> #define N 1100000 int next[N]; char str1[N]; int main(){ freopen("poj2406.in","r",stdin); freopen("poj2406.out","w",stdout); while (1){ scanf("%s",str1); if (str1[0]=='.') break; int n=strlen(str1); //get_next int i=0,j=-1;next[0]=-1; while (i<n){ if (j==-1||str1[i]==str1[j]){ ++i,++j;next[i]=j; }else j=next[j]; } //for (int i=0;i<=n;++i) printf("%d ",next[i]);printf("\n"); int ans=1; if (n%(n-next[n])==0) ans=n/(n-next[n]); printf("%d\n",ans); } return 0; }