POJ2406 Power Strings (给自己挖个坑先)

描述

注意,这一份后缀数组的代码并不能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
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/*
* ==============================================
*
* Filename: E.cpp
*
* Link: http://poj.org/problem?id=2406
*
* Version: 1.0
* Created: 2018/10/01 19时38分29秒
* Revision: MLE 不过好像用倍增的话会TLE
* Compiler: g++
*
* Author: 杜宁元 (https://duny31030.top/), duny31030@126.com
* Organization: QLU_浪在ACM
*
* ==============================================
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define pre(i,a,n) for(int i=n;i>=a;i--)
#define ll long long
#define max3(a,b,c) fmax(a,fmax(b,c))
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1001000;
int wa[N],wb[N],wv[N],wss[N];
int cmp(int *r,int a,int b,int l)
{
return r[a] == r[b] && r[a+l]==r[b+l];
}
int sa[N],rk[N],height[N];
int n;
char r[N];
int minnum[N][16];
void SA(char *r,int n,int m)
{
int *x = wa,*y = wb;

for(int i = 0;i < m;i++) wss[i] = 0;
for(int i = 0;i < n;i++) ++wss[x[i] = r[i]];
for(int i = 1;i < m;i++) wss[i] += wss[i-1];
for(int i = n-1;i >= 0;i--) sa[--wss[x[i]]] = i;

int p = 1;
for(int j = 1;p < n;j <<= 1,m = p)
{
p = 0;
for(int i = n-j;i < n;i++) y[p++] = i;
for(int i = 0;i < n;i++) if(sa[i] >= j) y[p++] = sa[i]-j;
for(int i = 0;i < n;i++) wv[i] = x[y[i]];
for(int i = 0;i < m;i++) wss[i] = 0;
for(int i = 0;i < n;i++) ++wss[wv[i]];
for(int i = 0;i < m;i++) wss[i] += wss[i-1];
for(int i = n-1;i >= 0;--i) sa[--wss[wv[i]]] = y[i];
swap(x,y); x[sa[0]] = 0; p = 1;
for(int i = 1;i < n;i++) x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p-1 : p++;
}

for(int i = 1;i < n;i++) rk[sa[i]] = i;
int k = 0;
for(int i = 0;i < n-1;height[rk[i++]] = k)
{
if(k) --k;
for(int j = sa[rk[i]-1];r[i+k] == r[j+k];k++);
}
}
void initRMQ()
{
int i,j;
int m = (int)(log(n*1.0)/log(n*2.0));
for(i = 1;i <= n;i++)
minnum[i][0] = height[i];
for(j = 1;j <= m;j++)
for(i = 1;i + (i<<j)-1 <= n;i++)
minnum[i][j] = min(minnum[i][j-1],minnum[i+(1<<(j-1))][j-1]);
}

int Ask_MIN(int a,int b)
{
int k = int(log(b-a+1.0)/log(2.0));
return min(minnum[a][k],minnum[b-(1<<k)+1][k]);
}

int lcp(int a,int b)
{
a = rk[a],b = rk[b];
if(a > b)
swap(a,b);
return Ask_MIN(a+1,b);
}

int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
int Maxn,k;
while(scanf("%s",r) && r[0] != '.')
{
// getchar();
Maxn = 1;
n = strlen(r);
r[n] = 0;

SA(r,n+1,130);
// calheight(r,sa,n+1);
initRMQ();
for(k = 1;k < n;k++) // 枚举长度
{
if(n%k)
continue;
int tmp = lcp(0,k);
if(tmp == n-k)
Maxn = max(Maxn,n/k);
}
printf("%d\n",Maxn);
}

fclose(stdin);
// fclose(stdout);
return 0;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
* ==============================================
*
* Filename: F.cpp
*
* Link: http://poj.org/problem?id=2406
*
* Version: 1.0
* Created: 2018/08/05 20时20分37秒
* Revision: none
* Compiler: g++
*
* Author: 杜宁元 (https://duny31030.top/), duny31030@126.com
* Organization: QLU_浪在ACM
*
* ==============================================
*/
#include <iostream>
#include <string.h>
#include <cstdio>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define pre(i,a,n) for(int i=a;i>=n;i--)
#define ll long long
#define max3(a,b,c) fmax(a,fmax(b,c))
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int N = 1000010;
char T[N];
int Next[N];
int tlen;

void get_Next()
{
int j,k;
j = 0; k = -1; Next[0] = -1;
while(j < tlen)
{
if(k == -1 || T[j] == T[k])
Next[++j] = ++k;
else
k = Next[k];
}
}

int main()
{
ios
#ifdef ONLINE_JUDGE
#else
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
while(scanf("%s",T))
{
if(T[0] == '.')
break;
tlen = strlen(T);
get_Next();
if(!Next[tlen])
printf("1\n");
else
{
int p = tlen-Next[tlen];
if(tlen%p == 0 && p)
printf("%d\n",tlen/p);
else
printf("1\n");
}
// rep(i,1,tlen)
// printf("%d%c",Next[i],i == tlen ? '\n' : ' ');
}
fclose(stdin);
// fclose(stdout);
return 0;
}