「POJ2406」Power Strings

Description

Given two strings a and b we define a×ba\times b to be their concatenation. For example, if a="abc"a = "abc" and b = “def” then a×b="abcdef"a\times b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a0=a^0 = “” (the empty string) and an+1=a×(an)a^{n+1} = a\times (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=ans = a^n for some string aa.

Sample Input

1
2
3
abcd
aaaa
ababab

Sample Output

1
2
3
1
4
3

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

题意

对于每组输入数据输出一行,找出每个字符串最多是由多少个相同的子字符串重复连接而成的。

Solution


根据nxtinxt_i的定义,中间由五条竖线的子串是相等的。
在字符串中,显然红色=红色,又红色=黄色,黄色=绿色…。最后就是红色=黄色=绿色=蓝色=紫色,构成了循环。
那么构成循环串的条件就是n0(modnnxtn)n\equiv 0\pmod {n-nxt_n}

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e6 + 999;
char s[N];
int n, nxt[N];

int main() {
while(~scanf("%s", s + 1)) {
if(s[1] == '.') break;
n = strlen(s + 1);
int j = 0;
for(int i = 2; i <= n; ++i) {
while(j && s[j + 1] != s[i]) j = nxt[j];
if(s[j + 1] == s[i]) ++j;
nxt[i] = j;
}
if(nxt[n] == 0 || nxt[n] % (n - nxt[n])) puts("1");
else writeln(n / (n - nxt[n]));
}
return 0;
}