题目链接:HDU 3746

HDU 3746 Cyclic Nacklace (KMP找循环节)-LMLPHP

Sample Input

3
aaa
abca
abcde

Sample Output

0
2
5

Author

Source

Solution

题意

给定一个字符串,问至少需要在末尾添加多少个字符使得字符串循环。

思路

KMP

设前缀函数为 \(\pi()\),字符串长度为 \(n\),下标从 \(1\) 开始。

最小循环节为 \(k = n - \pi(n)\)。

如果 \(n \% k=0\),那么字符串已经循环。

否则还需要添加 \(k - n \% k\) 个字符。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, pi[maxn];
char str[maxn]; void prefix_function() {
int j = 0;
for (int i = 2; i <= n; ++i) {
while (j > 0 && str[j+1] != str[i]) j = pi[j];
if (str[j+1] == str[i]) j++;
pi[i] = j;
}
} int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%s", str + 1);
n = strlen(str + 1);
prefix_function();
if(pi[n] == 0) {
printf("%d\n", n);
} else {
int k = n - pi[n];
if(n % k == 0) {
printf("0\n");
} else {
printf("%d\n", k - n % k);
}
}
}
return 0;
}
05-11 15:21
查看更多