浅谈\(KMP\)：https://www.cnblogs.com/AKMer/p/10438148.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=1355

跟POJ1961类似，答案就是\(n-nxt_n\)

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

using namespace std;

const int maxn=1e6+5;

int n;

char s[maxn];

int nxt[maxn];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

void make_nxt() {

    for(int j=0,i=2;i<=n;i++) {

        while(j&&s[j+1]!=s[i])j=nxt[j];

        if(s[j+1]==s[i])j++;nxt[i]=j;

    }

}

int main() {

    n=read();

    scanf("%s",s+1);

    make_nxt();

    printf("%d\n",n-nxt[n]);

    return 0;

}