[POI 12 Stage 2]Template

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

可以發現，能用來當模板的字串一定只能是主串的某個前綴

於是，我們可以枚舉前綴，然後看看這個前綴和字串中的哪些地方吻合
如果這些吻合的位置相鄰間的最大距離不超過這個前綴的長度，答案就是這個前綴的長度了

要怎麼得到這個前綴和字串中的哪些地方吻合呢？
就是$Z\ Value\geq$這個前綴長度的位置啦

$O(N)$將$Z\ Value$求出後，利用基數排序$O(N)$將它們由小到大排好
然後由短到長枚舉前綴，將$Z\ Value$太小的點刪掉
然後看看剩餘的點，相鄰間的最大距離是不是不超過這個前綴的長度

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

你問我為甚麼不需要考慮這個前綴是不是也是主串的後綴 (才能剛好覆蓋完整串)？
如果不是的話，鏈表中$N+1$這個點和前一個點的距離就爆掉啦～ ($>$目前前綴長度)

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

code:

#include<cstdio>
#include<cassert>
#include<algorithm>
#include<vector>
using namespace std;
void getmax(int &a,const int b){if(b>a)a=b;}
int N,Z[500000];
char S[500001];
int LEFT[500002],RIGHT[500002];
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%s",S);
    N=-1;while(S[++N]);
    Z[0]=0;
    for(int i=1,mx=0;i<N;i++)
    {
        if(mx+Z[mx]-1>=i)Z[i]=min(mx+Z[mx]-1-i+1,Z[i-mx]);
        else Z[i]=0;
        while(S[Z[i]]==S[i+Z[i]])Z[i]++;
        if(i+Z[i]>=mx+Z[mx])mx=i;
    }
    Z[0]=N;
//    for(int i=0;i<N;i++)printf("%d ",Z[i]);puts("");
    static vector<int>sort_buffer[500001];
    for(int i=0;i<=N;i++)sort_buffer[i].clear();
    for(int i=0;i<N;i++)sort_buffer[Z[i]].push_back(i);
    int ans=N+1;
    for(int i=0;i<=N;i++)LEFT[i+1]=i,RIGHT[i]=i+1;
    for(int len=0,max_gap=1;len<=N;len++)
    {
        if(len>=max_gap){ans=len;break;}
        for(int _i=0;_i<(int)sort_buffer[len].size();_i++)
        {
            const int i=sort_buffer[len][_i]+1;
            getmax(max_gap,RIGHT[i]-LEFT[i]);
            RIGHT[LEFT[i]]=RIGHT[i];
            LEFT[RIGHT[i]]=LEFT[i];
        }
    }
    assert(ans!=N+1);
    printf("%d\n",ans);
    return 0;
}