poj 2406 Power Strings 周期问题

2018-06-17 22:40:14来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

1
4
3

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])。
 
 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 char a[1000002];
 6 int p[1000002];
 7 void makep(int l)
 8 {
 9     memset(p,0,sizeof(p));
10     int j=0;
11     for(int i=1;i<l;i++)
12     {
13         while(a[i]!=a[j]&&j>0)
14         j=p[j-1];
15         if(a[i]==a[j])
16         j++;
17         p[i]=j;
18     }
19 }
20 void deal(int l)
21 {
22     int ans=1;
23         if(l%(l-p[l-1])==0)
24         ans=l/(l-p[l-1]);
25     printf("%d\n",ans);
26 }
27 int main()
28 {
29     while(scanf("%s",a)==1)
30     {
31         if(a[0]=='.')break;
32         int l=strlen(a);
33         makep(l);
34         deal(l);
35     }
36     return 0;
37 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:POJ 3311---Hie with the Pie(状压DP)

下一篇:P3414 SAC#1 - 组合数