描述
注意，这一份后缀数组的代码并不能AC
传送门：我是传送门
Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “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).
输入
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.
输出
For each s you should print the largest n such that s = a^n for some string a.
样例
输入
abcd
aaaa
ababab
.
输出
1
4
3
Note
This problem has huge input, use scanf instead of cin to avoid time limit exceed.
思路
用KMP找循环节的话，这是一道非常简单的题目
用后缀数组写的话好像必须用DC3算法。
我用倍增写的MLE了，理论上应该TLE。。。
我觉得应该是我的RMQ部分用的内存太多了，RMQ不需要求那么多，但是我还没仔细扣过这块，所以还是先留个坑，等我以后再回来填上
下附KMP代码
代码
后缀数组
1 /* 2 * ============================================== 3 * 4 * Filename: E.cpp 5 * 6 * Link: http://poj.org/problem?id=2406 7 * 8 * Version: 1.0 9 * Created: 2018/10/01 19时38分29秒 10 * Revision: MLE 不过好像用倍增的话会TLE 11 * Compiler: g++ 12 * 13 * Author: 杜宁元 (https://duny31030.top/), duny31030@126.com 14 * Organization: QLU_浪在ACM 15 * 16 * ============================================== 17 */ 18 #include<cstdio> 19 #include<cstdlib> 20 #include<cstring> 21 #include<cmath> 22 #include<algorithm> 23 #include<iostream> 24 using namespace std; 25 #define clr(a, x) memset(a, x, sizeof(a)) 26 #define rep(i,a,n) for(int i=a;i<=n;i++) 27 #define pre(i,a,n) for(int i=n;i>=a;i--) 28 #define ll long long 29 #define max3(a,b,c) fmax(a,fmax(b,c)) 30 #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 31 #define F(x) ((x)/3+((x)%3==1?0:tb)) 32 #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) 33 const double eps = 1e-6; 34 const int INF = 0x3f3f3f3f; 35 const int mod = 1e9 + 7; 36 const int N = 1001000; 37 int wa[N],wb[N],wv[N],wss[N]; 38 int cmp(int *r,int a,int b,int l) 39 { 40 return r[a] == r[b] && r[a+l]==r[b+l]; 41 } 42 int sa[N],rk[N],height[N]; 43 int n; 44 char r[N]; 45 int minnum[N][16]; 46 void SA(char *r,int n,int m) 47 { 48 int *x = wa,*y = wb; 49 50 for(int i = 0;i < m;i++) wss[i] = 0; 51 for(int i = 0;i < n;i++) ++wss[x[i] = r[i]]; 52 for(int i = 1;i < m;i++) wss[i] += wss[i-1]; 53 for(int i = n-1;i >= 0;i--) sa[--wss[x[i]]] = i; 54 55 int p = 1; 56 for(int j = 1;p < n;j <<= 1,m = p) 57 { 58 p = 0; 59 for(int i = n-j;i < n;i++) y[p++] = i; 60 for(int i = 0;i < n;i++) if(sa[i] >= j) y[p++] = sa[i]-j; 61 for(int i = 0;i < n;i++) wv[i] = x[y[i]]; 62 for(int i = 0;i < m;i++) wss[i] = 0; 63 for(int i = 0;i < n;i++) ++wss[wv[i]]; 64 for(int i = 0;i < m;i++) wss[i] += wss[i-1]; 65 for(int i = n-1;i >= 0;--i) sa[--wss[wv[i]]] = y[i]; 66 swap(x,y); x[sa[0]] = 0; p = 1; 67 for(int i = 1;i < n;i++) x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p-1 : p++; 68 } 69 70 for(int i = 1;i < n;i++) rk[sa[i]] = i; 71 int k = 0; 72 for(int i = 0;i < n-1;height[rk[i++]] = k) 73 { 74 if(k) --k; 75 for(int j = sa[rk[i]-1];r[i+k] == r[j+k];k++); 76 } 77 } 78 void initRMQ() 79 { 80 int i,j; 81 int m = (int)(log(n*1.0)/log(n*2.0)); 82 for(i = 1;i <= n;i++) 83 minnum[i][0] = height[i]; 84 for(j = 1;j <= m;j++) 85 for(i = 1;i + (i<<j)-1 <= n;i++) 86 minnum[i][j] = min(minnum[i][j-1],minnum[i+(1<<(j-1))][j-1]); 87 } 88 89 int Ask_MIN(int a,int b) 90 { 91 int k = int(log(b-a+1.0)/log(2.0)); 92 return min(minnum[a][k],minnum[b-(1<<k)+1][k]); 93 } 94 95 int lcp(int a,int b) 96 { 97 a = rk[a],b = rk[b]; 98 if(a > b) 99 swap(a,b); 100 return Ask_MIN(a+1,b); 101 } 102 103 int main() 104 { 105 #ifdef ONLINE_JUDGE 106 #else 107 freopen("in.txt","r",stdin); 108 // freopen("out.txt","w",stdout); 109 #endif 110 int Maxn,k; 111 while(scanf("%s",r) && r[0] != '.') 112 { 113 // getchar(); 114 Maxn = 1; 115 n = strlen(r); 116 r[n] = 0; 117 118 SA(r,n+1,130); 119 // calheight(r,sa,n+1); 120 initRMQ(); 121 for(k = 1;k < n;k++) // 枚举长度 122 { 123 if(n%k) 124 continue; 125 int tmp = lcp(0,k); 126 if(tmp == n-k) 127 Maxn = max(Maxn,n/k); 128 } 129 printf("%d ",Maxn); 130 } 131 132 fclose(stdin); 133 // fclose(stdout); 134 return 0; 135 }
KMP
1 /* 2 * ============================================== 3 * 4 * Filename: F.cpp 5 * 6 * Link: http://poj.org/problem?id=2406 7 * 8 * Version: 1.0 9 * Created: 2018/08/05 20时20分37秒 10 * Revision: none 11 * Compiler: g++ 12 * 13 * Author: 杜宁元 (https://duny31030.top/), duny31030@126.com 14 * Organization: QLU_浪在ACM 15 * 16 * ============================================== 17 */ 18 #include <iostream> 19 #include <string.h> 20 #include <cstdio> 21 using namespace std; 22 #define clr(a, x) memset(a, x, sizeof(a)) 23 #define rep(i,a,n) for(int i=a;i<=n;i++) 24 #define pre(i,a,n) for(int i=a;i>=n;i--) 25 #define ll long long 26 #define max3(a,b,c) fmax(a,fmax(b,c)) 27 #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 28 const double eps = 1e-6; 29 const int INF = 0x3f3f3f3f; 30 const int mod = 1e9 + 7; 31 32 const int N = 1000010; 33 char T[N]; 34 int Next[N]; 35 int tlen; 36 37 void get_Next() 38 { 39 int j,k; 40 j = 0; k = -1; Next[0] = -1; 41 while(j < tlen) 42 { 43 if(k == -1 || T[j] == T[k]) 44 Next[++j] = ++k; 45 else 46 k = Next[k]; 47 } 48 } 49 50 int main() 51 { 52 ios 53 #ifdef ONLINE_JUDGE 54 #else 55 freopen("in.txt","r",stdin); 56 // freopen("out.txt","w",stdout); 57 #endif 58 while(scanf("%s",T)) 59 { 60 if(T[0] == '.') 61 break; 62 tlen = strlen(T); 63 get_Next(); 64 if(!Next[tlen]) 65 printf("1 "); 66 else 67 { 68 int p = tlen-Next[tlen]; 69 if(tlen%p == 0 && p) 70 printf("%d ",tlen/p); 71 else 72 printf("1 "); 73 } 74 // rep(i,1,tlen) 75 // printf("%d%c",Next[i],i == tlen ? ' ' : ' '); 76 } 77 fclose(stdin); 78 // fclose(stdout); 79 return 0; 80 }