Cyclic Nacklace HDU - 3746
题意：
给你一个模式串。 判断加几个字符，可以使他变成有循环节的串。
思路：
求循环节
循环节 的传送门
先求出字符串的next。之后看最后一个字符的next。假如刚好可以凑成循环节，那么就输出ans。否则 补齐即可。（考虑abcabcab和 abca）
AC
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std
;
const int maxn
=1e5+10;
int nxt
[maxn
];
char s
[maxn
],p
[maxn
];
void getnxt(char *p
){
int m
= strlen(p
);
int i
=0,j
=-1;
nxt
[0]=-1;
while(i
<m
){
if(j
==-1||p
[i
]==p
[j
])nxt
[++i
]=++j
;
else j
=nxt
[j
];
}
}
int main()
{
ios
::sync_with_stdio(0);cin
.tie(0);cout
.tie(0);
int tt
;cin
>>tt
;
while(tt
--){
cin
>>p
;
getnxt(p
);
int m
= strlen(p
);
int res
=m
-nxt
[m
];
if( nxt
[m
]>0 && m
%res
==0 )cout
<<0<<endl
;
else cout
<<res
-m
%res
<<endl
;
}
return 0;
}
