hdu 3746 Cyclic Nacklace KMP循环节

Cyclic Nacklace

题意:给一个长度为Len( 3 <= Len <= 100000 )的英文串，问你在字符串后面最少添加几个字符可以使得添加后的串为周期串?

Sample Input

3

aaa

abca

abcde

 

Sample Output

0

2

5

 

思路:要是写过period再来写这道题会发现很简单；就是在getfail()得到f[]之后，贪心地看最后一个字符所能用到的最长后缀长度为多少?而这个后缀长度就是n - n%len;(n为字符串长度，len为循环节的长度)。当然事先要看是否本身就是一个循环串；时间复杂度O(n)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5 + 7;
char p[N];
int f[N];
void getfail(char *p,int *f)
{
    f[0] = f[1] = 0;
    int n = strlen(p);
    for(int i = 1;i < n;i++){
        int j = f[i];
        if(j && p[i] != p[j]) j = f[j];
        f[i+1] = (p[i] == p[j] ?j+1:0);// ｉ＋１会递推到第ｎ位
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s", p);
        getfail(p,f);
        int n = strlen(p),len = n - f[n];
        if(f[n] && n%len == 0) puts("0");//本身就是周期串
        else{
            printf("%d
",len-n%len);
        }
    }
}