poj-2406-Power Strings（KMP种next数组的应用，循环节）

题目链接：http://poj.org/problem?id=2406

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.

题目大意：重复输入字符串，对于每组字符串，输出有多少个最小的循环节，字符串能整除循环节；

仍是KMP中用next数组求循环节，求出的循环节要判断一下再输出；注意不要直接判断

例：aabbaabaa   显然应该使1，

ac：

#include<stdio.h>
#include<string.h>  
#include<math.h>  
  
//#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<iostream>  
#include<algorithm>  
using namespace std;  

#define ll long long  
#define INF 0x3f3f3f3f  
#define mod 998244353
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);
char p[1000100];
int next[1000100];

void get_next()
{
	next[0]=-1;
	int plen=strlen(p);
	int j=0,k=-1;
	while(j<plen)
	{
		if(k==-1||p[j]==p[k])
		{
			++j;
			++k;
			next[j]=k;
		}
		else
			k=next[k];
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	while(scanf("%s",&p))
	{
		if(strcmp(p,".")==0)
			break;
		get_next();
		int plen=strlen(p);
		int l=plen-next[plen];//最小循环节 
		if(plen%l==0)//循环节能被整除 
			printf("%d\n",plen/l);
		else
			printf("1\n");//不能的话只有一个 
	}
	
}