题目链接:HDU 3746
Sample Output
Author
possessor WC
Source
HDU 3rd “Vegetable-Birds Cup” Programming Open Contest
Solution
题意
给定一个字符串,问至少需要在末尾添加多少个字符使得字符串循环。
思路
KMP
设前缀函数为 $\pi()$,字符串长度为 $n$,下标从 $1$ 开始。
最小循环节为 $k = n - \pi(n)$。
如果 $n \% k=0$,那么字符串已经循环。
否则还需要添加 $k - n \% k$ 个字符。
Code
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
| #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; }
|