[POI 12 Stage 2] Template

作法：

首先求出每個點的 Z value ，假設$L$是一個答案，那就代表如果只看字串中那些 Z value $\geq L$的位子，這些位置的相鄰位置的差不會超過$L$。因此我們就可以考慮由小到大枚舉$L$，維護好當前有哪些位置的 Z value $\geq L$，並維護相鄰位置的差的最大值，用可以用個 set 做到這件事。每次把新的數移除的時候就看看他的左右兩個數，並拿這兩個數的差來更新當前的相鄰位置差的最大值。不過實際上用個 linked list 就可以了，複雜度降為$O(n)$。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10 ;
 
char s[maxn] ;
int n,Z[maxn] ;
void getz()
{
    Z[0]=-1 ;
    for(int i=1,L=-1,R=-1;s[i];i++)
    {
        int i2=i-L ;
        if(i>R)
        {
            int R2=i ;
            for(;R2<n && s[R2-i]==s[R2];R2++) ;
            Z[i]=R2-i ;
            L=i ; R=R2-1 ;
        }
        else if(Z[i2]>=R-i+1)
        {
            int R2=R ;
            for(;R2<n && s[R2-i]==s[R2];R2++) ;
            Z[i]=R2-i ;
            L=i ; R=R2-1 ;
        }
        else Z[i]=Z[i2] ;
//        printf("Z[%d] = %d\n",i,Z[i]) ;
    }
}
 
set<int> st ;
vector<int> v[maxn] ;
main()
{
    scanf("%s",s) ;
    n=strlen(s) ;
    getz() ;
    st.insert(0) ; st.insert(n) ;
    for(int i=1;i<n;i++) if(Z[i])
    {
        v[Z[i]].push_back(i) ;
        st.insert(i) ;
    }
 
    int ma=0 ;
    for(set<int>::iterator it=st.begin();;)
    {
        set<int>::iterator it0=it++ ;
        if(it==st.end()) break ;
        ma=max(ma,*it - *it0) ;
    }
    for(int i=1;i<=n;i++)
    {
        if(ma <= i){printf("%d\n",i) ; return 0 ;}
        for(int j=0;j<v[i].size();j++)
        {
            int x=v[i][j] ;
            set<int>::iterator it=st.find(x) , it1=it , it2=it ;
            it1-- ; it2++ ;
            ma=max(ma,*it2 - *it1) ;
            st.erase(it) ;
        }
    }
}