问题 D: Power Strings(Poj2406)
时间限制: 1 Sec 内存限制: 128 MB
提交: 27 解决: 10
[提交][状态][讨论版][命题人:add_cst][Edit] [TestData]
题目链接:http://acm.ocrosoft.com/problem.php?cid=1717&pid=3
题目描述
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).
输入
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.
输出
For each s you should print the largest n such that s = a^n for some string a.
样例输入
abcd
aaaa
ababab
.
样例输出
1
4
3
思路:说那么长,其实难点就是在求整个字符串的最大匹配长度。
因为最大匹配长度是前缀等于后缀,所以向后遍历【原式长度-最大匹配长度】一定会发生重复。
So,答案就是原式长度/(原式长度-最大匹配长度)。
代码:
#include<bits/stdc++.h>
using namespace std;
int Next[1000000];
void get_next(string child)
{
memset(Next, 0, sizeof(Next));
int i = 0;
int j = -1;
Next[0] = -1;
while (i < child.length())
{
if (j == -1 || child[i] == child[j])
{
++i;
++j;
Next[i] = j;
}
else
{
j = Next[j];
}
}
}
int main()
{
string child;
while (cin >> child && child[0] != '.')
{
memset(Next, 0, sizeof(Next));
get_next(child);
int n = child.length();
if(n % (n - Next[n])==0)
cout << n / (n - Next[n]) << endl;//原式长度/(原式长度-最大匹配长度)
else cout << 1 << endl;
}
}