题意:
求从末端补足至少两周期的最小项数.
思路:
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); } }