HDU-3746 Cyclic Nacklace 字符串匹配 KMP算法 求最小循环节

题目链接: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
上一篇:干货 | 基于Go SDK操作京东云对象存储OSS的入门指南


下一篇:Young Table(暴力,交换位置)