[POI 12 Stage 2]Template

這裡提供了另外一個做法，選個喜歡的去實現吧～

可以發現，能用來當模板的字串一定只能同時是主串的前綴和後綴
回顧$KMP$中失配函數$fail$ (有人稱作$next$) 的定義：(以下字串中的編號皆由$0$開始)
字串$S$的$fail[i]$代表$S$的最長前綴長度，使得這個前綴和$S_{0\sim i-1}$的後綴 (結尾是$i-1$的子串) 完全相符

於是，可以當作答案的前綴的長度就只能是$N$、$fail[N]$、$fail[fail[N]]$、......了 ($N$為主串長度)
把這些候選人依序存起來，$f_{0}=N$、$f_{1}=fail[N]$、$f_{2}=fail[fail[N]]$、......、$f_{n}=0$

於是，我們可以從$f_{n-1}$開始枚舉候選人 ($f_{n}=0$代表空串，是不合法的)，看看和$S_{0\sim f_{i}-1}$匹配的點中，相鄰點間的最大距離有沒有超過$f_{i}$，沒有的話答案就是$f_{i}$

注意，和這個作法不一樣的是，這些點代表的是字串尾端的位置 (也就是代表以這個點為結尾的子串)，而不是字串開頭的位置

與其找出所有和$S_{0\sim f_{i}-1}$匹配的點，不如改成只保留和$S_{0\sim f_{i}-1}$匹配的點

做法是：
先將所有$fail$的邊反向建圖，我們就得到了一棵根為$0$的樹
可以發現，對於任何一個節點$u$，和以$u$為根的子樹中任何一個節點$v$，$S_{v-u\sim v-1}$和$S_{0\sim u-1}$匹配

當枚舉到$f_{i}$這個候選人，就將$f_{i+1}$所有不包含$f_{i}$的子樹中涵蓋的點全部刪除 (因為這些點和$S_{0\sim f_{i+1}}$匹配，但不和$S_{0\sim f_{i}}$匹配)
這樣每一個點都只會被刪掉一次，沒有重複也沒有遺漏 (除了$N$這個最後的點)

利用雙向鏈表可以實現$O(1)$刪點並維護相鄰點間的最大距離

時間複雜度：$O(N)$

code:

#include<cstdio>
#include<cassert>
#include<vector>
using namespace std;
void getmax(int &a,const int b){if(b>a)a=b;}
void BuildFail(const char *str,int *fail)
{
    fail[0]=fail[1]=0;
    for(int i=1;str[i];i++)
    {
        int &f=fail[i+1]=fail[i];
        while(f&&str[f]!=str[i])f=fail[f];
        if(str[f]==str[i])f++;
    }
}
int N,FAIL[500001],LEFT[500002],RIGHT[500002];
char S[500001];
vector<int>ET[500001];
void RemoveNode(const int _loc,int &max_len)
{
//    printf("remove %d\n",_loc);
    const int loc=_loc+1;
    getmax(max_len,RIGHT[loc]-LEFT[loc]);
    RIGHT[LEFT[loc]]=RIGHT[loc],LEFT[RIGHT[loc]]=LEFT[loc];
}
void RemoveNodes(const int u,int &max_len)
{
    RemoveNode(u,max_len);
    for(int i=0;i<(int)ET[u].size();i++)RemoveNodes(ET[u][i],max_len);
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%s",S);
    N=-1;while(S[++N]);
    BuildFail(S,FAIL);
    for(int i=0;i<=N;i++)ET[i].clear();
    for(int i=1;i<=N;i++)ET[FAIL[i]].push_back(i);
    vector<int>valid_prefixes;
    for(int cur=N;cur;cur=FAIL[cur])valid_prefixes.push_back(cur);
    valid_prefixes.push_back(0);
    for(int i=0;i<=N;i++)LEFT[i+1]=i,RIGHT[i]=i+1;
    int ans=N,max_len=1;
    for(int i=(int)valid_prefixes.size()-1;i>0;i--)
    {
        const int root=valid_prefixes[i],exclude=valid_prefixes[i-1];
//        printf("root=%d,max_len=%d\n",root,max_len);
        if(root>=max_len){ans=root;break;}
        for(int j=0;j<(int)ET[root].size();j++)if(ET[root][j]!=exclude)RemoveNodes(ET[root][j],max_len);
    }
    printf("%d\n",ans);
    return 0;
}