题目链接:https://cn.vjudge.net/problem/HDU-3746
题意
给一串珠子,我们可以在珠子的最右端或最左端加一些珠子
问做一条包含循环珠子的项链,最少还需要多少珠子
思路
KMP的另一个用法,求最小循环节minloop=len-fail[len]
用我的观点来看KMP的fail数组,就是值域和定义域都是串的长度,返回值是这个串能够匹配后缀的最大前缀串长度
但是纯循环节构成的串中,这个返回值不包括第一个循环节
比如aabaabaab
fail[9]6 fail[6]3
提交过程
WA | 没有注意至少两个循环节 |
AC |
代码
#include <cstring>
#include <cstdio>
const int maxm=1e5+20;
char P[maxm];
int fail[maxm];
// the domain and range of fail array mean the length of correct string.
void getFail(int m){
fail[0]=fail[1]=0;
for (int i=1; i<m; i++){
int j=fail[i];
while (j && P[j]!=P[i]) j=fail[j];
fail[i+1]=((P[i]==P[j])?j+1:0);
}
}
int main(void){
int T, len;
scanf("%d", &T);
while (T--){
scanf("%s", P);
getFail(len=strlen(P));
int maxloop=len-fail[len];
if (len%maxloop) printf("%d\n", maxloop-len%maxloop);
else printf("%d\n", (len==maxloop)?maxloop:0);
}
return 0;
}
Time | Memory | Length | Lang | Submitted |
---|---|---|---|---|
109ms | 1688kB | 581 | G++ | 2018-08-02 10:35:30 |