[HDU 3746]Cyclic Nacklace[kmp求周期]

发布时间:2016-12-9 13:53:04 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"[HDU 3746]Cyclic Nacklace[kmp求周期]",主要涉及到[HDU 3746]Cyclic Nacklace[kmp求周期]方面的内容,对于[HDU 3746]Cyclic Nacklace[kmp求周期]感兴趣的同学可以参考一下。

题意: 求从末端补足至少两周期的最小项数. 思路: kmp求循环周期应用 #include <cstring> #include <cstdio> const int MAXN = 100005; int next[MAXN]; char s[MAXN]; //125MS 688K void prekmp() { next[0] = -1; int j = -1; for(int i=1;s[i];i++) { while(j!=-1 && s[j+1]!=s[i]) j = next[j]; if(s[j+1]==s[i]) j++; next[i] = j; } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",s); prekmp(); int n,len,r,q,add; n = strlen(s); len = n - 1 - next[n-1]; r = n % len; q = n / len; if(q==1) { add = 2*len - n; } else { add = (len - r)%len; } printf("%d\n",add); } }

上一篇:
下一篇:JSON解析

相关文章

相关评论