poj 2406 Power Strings 周期问题

Power Strings

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 48139		Accepted: 20040

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

Hint

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

Source

Waterloo local 2002.07.01

百度扯淡：

内存限制：时间限制：3000ms 65536k

意见：总48139 20040接受：

描述

我们给出两个字符串A和B是定义了他们的concatenation *。例如，如果A和B =“abc”，然后在“def”=“*（ABCDEF）”。如果我们想到的exponentiation concatenation繁殖，用非负整数的定义为：在正常的方式（0 =“”（空字符串）和（N + 1）=（n×公尺）。

输入

每个测试用例的输入线，代表的是一个可打印的字符，字符串）。S的长度将至少1百万的人物将不超过1。含周期线为最后的测试案例。

输出
你应该为每个打印最大的N，S = N次这样的一些字符串。

样本输入
ABCD
AAAA
ABABAB
.
示例输出
1
4
3
提示
这个问题有巨大的投入，而不是使用scanf的CIN，避免超过时间限制。
源代码
当地的2002.07.01滑铁卢

假设 S 的周期大于 1。假设 S 存在周期 X，而且每
个周期的长度为 L。那么，我们有 S[1..n-L] = S[L+1…n]，
对于 i=n 来说，n-L 是一个合法的 j。
* 由于 P 数组所求的是所有 j 的最大值，所以只要判断 P[n] 即
可。如果 P[n] < n/2，则说明 S 不存在周期；否则最小的周期
长度为 n-p[n]，对应的周期为 n / (n – p[n])。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 char a[];

 int p[];

 void makep(int l)

 {

     memset(p,,sizeof(p));

     int j=;

     for(int i=;i<l;i++)

     {

         while(a[i]!=a[j]&&j>)

         j=p[j-];

         if(a[i]==a[j])

         j++;

         p[i]=j;

     }

 }

 void deal(int l)

 {

     int ans=;

         if(l%(l-p[l-])==)

         ans=l/(l-p[l-]);

     printf("%d\n",ans);

 }

 int main()

 {

     while(scanf("%s",a)==)

     {

         if(a[]=='.')break;

         int l=strlen(a);

         makep(l);

         deal(l);

     }

     return ;

 }

巴特西

poj 2406 Power Strings 周期问题

最新文章

热门文章