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.
Source
【分析】
其实我是来贴诗句的。。
/*
唐代李白
《三五七言 / 秋风词》 秋风清，秋月明，
落叶聚还散，寒鸦栖复惊。
相思相见知何日？此时此夜难为情！
入我相思门，知我相思苦。
长相思兮长相忆，短相思兮无穷极。
早知如此绊人心，何如当初莫相识。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map>
#include <ctime>
#include <cstdlib>
#include <stack>
#define LOCAL
const int MAXN = + ;
const int INF = ;
const int SIZE = ;
const int MAXM = + ;
const int maxnode = 0x7fffffff + ;
using namespace std;
int l1, l2;
char a[MAXN], b[MAXN];
int next[];//不用开太大了..
void getNext(){
//初始化next数组
next[] = ;
int j = ;
for (int i = ; i <= l1; i++){
while (j > && a[j + ] != a[i]) j = next[j];
if (a[j + ] == a[i]) j++;
next[i] = j;
}
return;
}
int kmp(){
int j = , cnt = ;
for (int i = ; i <= l2; i++){
while (j > && a[j + ] != b[i]) j = next[j];
if (a[j + ] == b[i]) j++;
if (j == l1){
cnt++;
j = next[j];//回到上一个匹配点
}
}
return cnt;
} void init(){
scanf("%s", a + );
scanf("%s", b + );
l1 = strlen(a + );
l2 = strlen(b + );
} int main(){
int T; while (scanf("%s", a + )){
if (a[] == '.') break;
l1 = strlen(a + );
getNext();
if (l1%(l1 - next[l1]) == ) printf("%d\n", l1/(l1 - next[l1]));
else printf("1\n");
}
return ;
}