Power Strings
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 67639 Accepted: 27893

Description

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

题目大意：
给你长度为n的字符串问你它的最大循环节个数是多少？
思路：
next数组求最大前后缀，然后总长度-next[尾]=循环节个数，然后总长度/循环节个数就是我们要的答案，但是需要判断一下他是否是循环节用模运算判断就好了。
代码：

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

string str;
vector<int> getnext(string str){
	vector<int>next(str.size());
	for(int j=1,k=0;j<str.size();j++){
		while(k>0&&str[j]!=str[k]){
			k=next[k-1];
		}
		if(str[j]==str[k]){
			next[j]=++k;
		}else{
			next[j]=k;
		}
	}
	return next;
}
int main(){
	while(cin>>str&&str[0]!='.'){
		vector<int>next=getnext(str);
		int maxlen=1;
		int len=str.size()-next[str.size()-1];
		int l=str.size()/len;
		if(str.size()%len==0)//需要判断一下我们只要满足循环的才要不满足的就是1
		maxlen=max(maxlen,l);
		//一开始以为在所有字串找最大循环节个数，后面慢慢才知道是找整个串的 
		/*for(int i=0;i<str.size();i++){ //printf("%d ",next[i]); int l=(i+1)-next[i]; if((i+1)%l==0) maxlen=max(maxlen,(i+1)/l); }*/
		
		printf("%d\n",maxlen);
	}
}