首先，我们来观察一下fail数组（不知道fail数组的请访问:KMP算法详解），我们发现一个串若是一个可以有一个子串多次拼接而成的，则其fail数组的值一定是从第一次循环这个子串的那一位依次递增，同时这个子串一定是这个串的最小的循环节。
所以我们根据这个性质，可以解决不少问题
poj 2406：
Power Strings
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 45261 | Accepted: 18886 |
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
题解：
这个题的意思是说给你一个串，问你这个串需要多少个最小循环节才能构成
很明显，我们只需要求一下fail数组即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s2[2333333];
char s1[2333333];
int fail[2333333];
void init(int m)
{
fail[1] = 0;
for (int i = 2; i <= m; i++)
{
int p = fail[i-1];
while (p && s2[p+1] != s2[i])
p = fail[p];
if (s2[p+1] == s2[i])
p++;
fail[i] = p;
}
}
int main()
{
while (scanf("%s", s2+1) != EOF)
{
if (s2[1] == '.')
break;
memset(fail, 0, sizeof(fail));
int m = strlen(s2 + 1);
init(m);
int pos = 0;
pos = m - fail[m];
int ans = m / pos;
if (m % pos != 0 || m == pos)
ans = 1;
cout << ans << endl;
}
return 0;
}
poj 1961
Period
| Time Limit: 3000MS | Memory Limit: 30000K | |
| Total Submissions: 16832 | Accepted: 8097 |
Description
For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK ,that is A concatenated K times, for some string A. Of course, we also want to know the period K.
Input
The input consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S.The second line contains the string S. The input file ends with a line, having the
number zero on it.
number zero on it.
Output
For each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.
Sample Input
3 aaa 12 aabaabaabaab 0
Sample Output
Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4
题解:
题意和2406的题意差不多，但它求的是对于每一位（大于1）往前的串的最小循环节的数量。所以外面还要多套一层for
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s1[1000005];
char s2[1000005];
int fail[1000005];
void init(int m)
{
fail[1] = 0;
for (int i = 2; i <= m; i++)
{
int p = fail[i - 1];
while (p && s1[p+1] != s1[i])
p = fail[p];
if (s1[i] == s1[p + 1])
p++;
fail[i] = p;
}
}
int main()
{
int n, cnt = 0;
while (scanf("%d", &n) != EOF)
{
if (n == 0)
break;
for (int i = 1; i <= n; i++)
fail[i] = 0;
cnt++;
printf("Test case #%d\n", cnt);
scanf("%s", s1+1);
for (int i = 1; i <= n; i++)
s2[i] = s1[i];
init(n);
for (int i = 2; i <= n; i++)
{
int pos = i - fail[i];
if (i % pos != 0 || i == pos)
continue;
printf("%d %d\n", i, i / pos);
}
puts("");
}
return 0;
}