Border——BZOJ1355 [Baltic2009]Radio Transmission

http://www.lydsy.com/JudgeOnline/problem.php?id=1355

這個題一開始我樣例解釋根本看不懂，其實這個解釋是錯的（也沒必要看）

我來重新解釋一下這個樣例吧

8

cabcabca

這個串是cabcabcab的子串對吧，那麼就是cab不斷自我連接配接得到，答案是3

首先我們來看一下，cabcabca這個串的最大border（除了自己）是5（就是cabca是不是）

把原串減掉字尾border最大子串，我們發現剩下的子串就是循環節cab！

再舉個樣例：

10

abcdabcdab

這個串的最大border是6（abcdab）減掉以後，剩下的子串abcd也是循環節！

根據猜想我們就可以确定答案就是串長-最大border

證明：我們可以把字元串看成是p段循環節（最後的剩餘部分看成p+1）每段循環節看成a[i]

因為最後的剩餘部分一定是循環節的字首，每個循環節又相等，是以原串的最大border是a[1~p-1]+剩餘部分

這個東西等于a[2~p]+剩餘部分，也就是到串尾！

剩下的就是循環節a[1]啊

循環節不就是串長-border嗎

然後這題就變成了大水題

#include<bits/stdc++.h>
using namespace std;
char a[];
int nex[];
int main()
{
    int n;scanf("%d",&n);
    scanf("%s",a+);
    int j=;
    for(int i=;i<=n;i++){
        while(j&&a[i]!=a[j+])j=nex[j];
        if(a[i]==a[j+])j++;
        nex[i]=j;
    }
    printf("%d",n-nex[n]);
    return ;
}