Power Strings.0 KMP

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.

在这里插入代码#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; char f[1001000]; int m,n,nt[1001000]; void gnt(char f[]) { int i=0,j=nt[0]=-1; while(i<m) { if(j==-1||f[i]==f[j])//不发生匹配或i和j发生匹配要向右移动一位  { i++;j++; nt[i]=j;//最大前缀和最大后缀的匹配长度  } else j=nt[j];//回溯到之前不匹配的位置  } } int main() { while(~scanf("%s",f)) { if(f[0]=='.') break; m=strlen(f); gnt(f); n=m-nt[m];//最小循环节长度  if(m%n==0) printf("%d\n",m/n);//求有几个循环节  else printf("1\n"); } return 0; }片 

本文地址：https://blog.csdn.net/nearal/article/details/107893068