Power Strings
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
题目类型：KMP中Next数组应用
算法分析：直接计算出输入字符串的Next数组，然后判断len % (len – Next[len])是否为0，如果为0，则len / (len – Next[len])即为最后的答案，否则结果为1
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int INF = 0x7FFFFFFF; const int maxn = 1000000 + 66; int Next[maxn], len; string s; void Build () { Next[0] = -1, Next[1] = 0; int k = 0, i; for (i = 2; i <= len; i++) { while (k >= 0 && s[i-1] != s[k]) k = Next[k]; Next[i] = ++k; } } int main() { // ifstream cin ("aaa.txt"); while (cin >> s) { if (s == ".") break; len = s.length (); Build (); if (len % (len - Next[len]) == 0) cout << len / (len - Next[len]) << endl; else cout << "1" << endl; } return 0; } |
- « 上一篇：poj2387
- poj2417：下一篇 »