Problem 1011 Power Strings

来源:http://acm.fzu.edu.cn/problem.php?pid=1011
Problem Description
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).

Each test case is a line of input representing s, a string of printable characters. For each s you should print the largest n such that s = a^n for some string a. 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.

1
2
3
4
5
6
7
8
9
 Sample Input
abcd
aaaa
ababab
.
Sample Output
1
4
3

思路:刚开始以为挺简单的,字符串的一个循环搜索就好了,结果输入数据是100W。。。一开始没看到100W,设置数组为10W,结果无限的运行时错误,百度看了大神的思路,大部分KMP。。。这个算法我一点不懂,,尝试看了下。。。也没看懂。以后有空去问问老师这个算法吧。。。然后找了一会 发现一个间接的方案。。
首先关于字符串是否能时重复的,那么这个重复的子字符串的长度必然是总长度的公因子。所以,取于判断是否可以整除就可以减掉大部分无意义的运算,然后循环对比字符串,找到循环因子即可。对了,千万不要用C++的 cin 他处理100W的字符串输入就需要10S左右,肯定超时,如果要用就要先 std::ios::sync_with_stdio(false);使得C++的cin直接输入,而不是在缓存中到输入结束在输入到变量中。
大神博客地址:http://blog.csdn.net/shiwaigaoren12345/article/details/50517786
下面是我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <cstring>
char a[1001001];
int main() {
int i, j, k, len, flag;
while (scanf("%s",a)) {
if (a[0] == '.')break;
len = strlen(a);
for (i = 1; i<=len; i++) {
flag = 1;
if (len%i == 0) {
for ( k = i; k < len; k++)
{
if (a[k%i] != a[k]) {
flag = 0;
break;
}
}
if (flag) {
printf("%d\n", len / i);
break;
}
}
}
}
return 0;
}

C++ 的 cin版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstring>
using namespace std;
char a[1001001];
int main() {
int i, j, k, len, flag;
std::ios::sync_with_stdio(false);
while (cin >> a && a[0] != '.') {
len = strlen(a);
for (i = 1; i<=len; i++) {
flag = 1;
if (len%i == 0) {
for ( k = i; k < len; k++)
{
if (a[k%i] != a[k]) {
flag = 0;
break;
}
}
if (flag) {
cout << len / i << endl;
break;
}
}
}
}
return 0;
}