POJ2406 Power Strings(KMP)

题目链接:点我

---

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). 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.

---

题意:

给你一串字符串,找出它是由某个字符串循环多少次构成的,

思路:

KMP算法,裸题,算出next[len] 即可得出答案,

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn = 1e6+10; char s[maxn]; int nextt[maxn]; void getnextt(int len){ memset(nextt, 0, sizeof(nextt)); nextt[0] = -1; int i = 0; int j = -1; while(i < len){ if(j == -1 || s[i] == s[j]){ ++i; ++j; if(s[i] != s[j]) nextt[i] = j; else nextt[i] = nextt[j]; }else j = nextt[j]; } } int main(){ // std::ios::sync_with_stdio(false); while(cin>>s && s[0] != '.'){ int len = strlen(s); getnextt(len); int ans = len/(len - nextt[len]); if(len % (len - nextt[len]) != 0)//特殊情况 ans = 1; printf("%d\n",ans); }return 0; }