YbtOJ 544「后缀自动机」子串选取

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
Cn int N=5e5+10,M=sqrt(2*N);
int n,a[N],OW[2][N],Ans,f[N];char s[N];
struct Base{int pw,md;}o[2];
struct HashX{int x,y;}h[N];
I HashX operator+(Cn HashX& A,CI v){return (HashX){(1LL*A.x*o[0].pw%o[0].md+v)%o[0].md,(1LL*A.y*o[1].pw%o[1].md+v)%o[1].md};}
I bool operator==(Cn HashX& A,Cn HashX& B){return A.x==B.x&&A.y==B.y;}
I HashX Hash(CI l,CI r){return (HashX){(h[r].x+o[0].md-1LL*h[l-1].x*OW[0][r-l+1]%o[0].md)%o[0].md,(h[r].y+o[1].md-1LL*h[l-1].y*OW[1][r-l+1]%o[1].md)%o[1].md};}
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
vector<PA> q[N];
#define pb push_back
I bool operator<(Cn HashX& A,Cn HashX &B){return A.x^B.x?A.x<B.x:A.y<B.y;}
map<HashX,bool> mp[M];
struct HashTable{
    int fir[19260818],nxt[N*4],val[N*4],w[N*4],tot;
    I void Add(Cn HashX& z){nxt[++tot]=fir[z.x],fir[z.x]=tot,w[tot]=z.y;}
    I int Q(Cn HashX& z){RI i;for(i=fir[z.x];i;i=nxt[i]) if(w[i]==z.y) return 1;return 0;}
}H;
int main(){
    freopen("substr.in","r",stdin),freopen("substr.out","w",stdout);
    RI i,j,mx,t;for(scanf("%d",&n),mx=sqrt(2*n),scanf("%s",s+1),o[0]=(Base){233,19260817},o[1]=(Base){31,19260817},i=1;i<=n;i++) a[i]=s[n-i+1]-'a'+1,h[i]=h[i-1]+a[i];
    for(OW[0][0]=OW[1][0]=i=1;i<=n;i++) OW[0][i]=1LL*OW[0][i-1]*o[0].pw%o[0].md,OW[1][i]=1LL*OW[1][i-1]*o[1].pw%o[1].md;for(H.Add((HashX){0,0}),i=1;i<=n;i++){
        for(t=f[i-1]+1;!H.Q(Hash(i-t+2,i))&&!H.Q(Hash(i-t+1,i-1));){
            t--;for(j=f[i-t];j>=1&&!H.Q(Hash(i-t-j+1,i-t));j--) H.Add(Hash(i-t-j+1,i-t));
        }Ans=max(Ans,(f[i]=t));
    }return printf("%d\n",Ans),cerr<<clock()<<'\n',0;
}