首页 > 代码库 > Power Strings (poj 2406 KMP)

Power Strings (poj 2406 KMP)

2024-07-28 21:51:52   213人阅读

Language:
Power Strings
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 33205 Accepted: 13804

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

abcdaaaaababab.

Sample Output

143

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

Source

Waterloo local 2002.07.01

题意：给一个字符串S长度不超过10^6，求最大的n使得S由n个相同的字符串a连接而成，如："ababab"则由n=3个"ab"连接而成，"aaaa"由n=4个"a"连接而成，"abcd"则由n=1个"abcd"连接而成。

定理：假设S的长度为len，则S存在循环子串，当且仅当，len可以被len - next[len]整除，最短循环子串为S[len - next[len]]

思路：利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，则最大循环次数n为len/(len - next[len])，否则为1。

代码：

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <string> 7 #include <map> 8 #include <stack> 9 #include <vector>10 #include <set>11 #include <queue>12 #pragma comment (linker,"/STACK:102400000,102400000")13 #define maxn 100514 #define MAXN 200515 #define mod 100000000916 #define INF 0x3f3f3f3f17 #define pi acos(-1.0)18 #define eps 1e-619 typedef long long ll;20 using namespace std;21 22 int N;23 int nextval[1000010];24 char str[1000010];25 26 int get_nextval()27 {28     int i=0;29     int len=strlen(str);30     int j=-1;31     nextval[i]=-1;32     while (i<len)33     {34         if (j==-1||str[i]==str[j])35         {36             i++;37             j++;38             nextval[i]=j;39         }40         else41             j=nextval[j];42     }43     if ((len)%(len-nextval[len])==0)44         return len/(len-nextval[len]);45     else46         return 1;47 }48 49 int main()50 {51     while (scanf("%s",str))52     {53         if (str[0]==‘.‘)54             return 0;55         printf("%d\n",get_nextval());56     }57     return 0;58 }
View Code

 

Power Strings (poj 2406 KMP)


联系
我们