#include<iostream>
#include<cstring>
using namespace std;
int len;
void getNext(char *s, int *nex)
{
nex[0] = -1;
int i = 0, j = -1;
while(i < len)
{
if(j == -1 || s[i] == s[j])
{
i++, j++;
nex[i] = j;
}
else j = nex[j];
}
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
char s[100100];
scanf("%s", s);
len = strlen(s);
int nex[100100];
getNext(s, nex);
int a = nex[len];
if(2*a < len) printf("%d\n", len-2*a); //第一种情况,后面直接补
else if(len%(len-a) == 0) printf("0\n"); //正好
else printf("%d\n", len-a-(len%(len-a))); //循环节为len-a,前面开头那段
}
//system("pause");
return 0;
}
相关文章
- 03-26HDU 3746 Cyclic Nacklace KMP
- 03-26HDU 3746 (KMP求最小循环节) Cyclic Nacklace
- 03-26HDU3746 Cyclic Nacklace 【KMP】
- 03-26hdu-----(3746)Cyclic Nacklace(kmp)
- 03-26HDU3746 Cyclic Nacklace —— KMP 最小循环节
- 03-26Cyclic Nacklace[HDU3746]
- 03-26[KMP求最小循环节][HDU3746][Cyclic Nacklace]
- 03-26HDU 3746 - Cyclic Nacklace & HDU 1358 - Period - [KMP求最小循环节]
- 03-26hdoj 3746 Cyclic Nacklace【KMP求在结尾加上多少个字符可以使字符串至少有两次循环】
- 03-26Match:Cyclic Nacklace(KMP的next数组的高级应用)(HDU 3746)