[POI XIII Stage 1][KMP] Periods of Words

原題連結
字串的一題基礎題
題目要求是：
定義F(S)是最長的字串A的長度，使得A是S的前綴且S是AA的前綴且A不為S，求S的所有前綴的F總和。

先寫下一些簡單的推導：(以下大寫字母皆代表某字串)
依據題目要求，假設S=AB，則有AA=SC=ABC，即A=BC，代回S有S=BCB。
那麼問題轉化為：求出最短的非空字串B使得B是S的後綴也是S的前綴。

有沒有覺得很像KMP?只是KMP是求最長的B，那要怎麼做出最短呢？

根據fail函數的性質不難發現，若fail[a_0]=a_1,fail[a_1]=a_2,....fail[a_x]=-1，也就是從a_0沿著fail往回走的過程中，最短的B其實就是發生在a_x這個位置(想一想，為什麼)

而且fail指針又會是一棵樹，這讓我們聯想到dp：用dp[i]表示i這個位置的答案，那麼所有沿著fail來到i的人都可以用i去更新自己。

這樣子，每個狀態(位置)都只會經過1次，時間複雜度是O(n)。

#define LL long long
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const LL maxn=1000000+5;
const LL INF=(1<<30);
LL fail[maxn],dp[maxn];
LL DP(LL now)
{
    if(dp[now]!=-1) return dp[now];
    dp[now]=INF;
    if(fail[now]==-1) return dp[now]=now;
    if(fail[now]==0) return dp[now]=0;
    return dp[now]=min(dp[now],DP(fail[now]));
}
void getfail(char* s)
{
    LL cur=fail[0]=-1,n=strlen(s),ans=0;
    for(LL i=1;i<n;i++)
    {
        while(cur!=-1 && s[cur+1]!=s[i]) cur=fail[cur];
        if(s[cur+1]==s[i]) cur++;
        fail[i]=cur;
//        printf("fail[%lld]=%lld\n",i,fail[i]);
    }
    memset(dp,-1,sizeof dp);
    for(LL i=1;i<n;i++)
    {
//        printf("dp[%lld]=%lld\n",i,DP(i));
        if(DP(i)!=INF) ans+=i-DP(i);
    }
    printf("%lld\n",ans);
}
char s[maxn];
int main()
{
    LL n;
    scanf("%lld%s",&n,s);
    getfail(s);
}