Cool Slogans[CF700E][后缀自动机][Dp]

题目

Luogu

$n\le 2?10^5$

思路

性质：$?s_i$ 是 $s_{i?1}$ 的后缀
如图

那么此时可以缩短 $s_{i?1}$

然后联系后缀自动机不难想到是祖先关系

设 $s_{i?1}$ 代表结点为 $u$
设 $s_i$ 代表结点为 $v$
有 $endpos(v)\in endpos(u)$
由于是后缀，必定出现一次
现在还要找一次

如图，黑色的是 $endpos(v)$ 所有的是 $endpos(u)$
那么任意找一个 $x\in endpos(v)$ 后找 $[x?maxle{n}_v+maxle{n}_u,x?1]$ 中出现一个即可
线段树合并即可

代码

//#pragma GCC optimize(2)
#include<set>
#include<map>
#include<stack>
#include<ctime>
#include<cstdio> 
#include<queue> 
#include<cmath> 
#include<vector> 
#include<cstring> 
#include<climits> 
#include<iostream> 
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9'){
    x=x*10+c-'0';c=getchar();}return f*x;
}
#define MAXN 600000
#define INF 0x3f3f3f3f
int ed[MAXN+5];
int Root,scnt,lst,maxlen[MAXN+5],nxt[MAXN+5][27],fail[MAXN+5];
int Newnode(){
    int u=++scnt;fail[u]=0,maxlen[u]=0;memset(nxt[u],0,sizeof(nxt[u]));return u;
}
void Init(){
    scnt=0;Root=lst=Newnode();return ;
}
void Extend(int c,int id){
    int p=lst,cur=(lst=Newnode());ed[cur]=id;maxlen[cur]=maxlen[p]+1;while(p&&!nxt[p][c])nxt[p][c]=cur,p=fail[p];if(!p){
    fail[cur]=1;return ;}int q=nxt[p][c];if(maxlen[q]==maxlen[p]+1){
    fail[cur]=q;return ;}int clone=Newnode();ed[clone]=id;maxlen[clone]=maxlen[p]+1;memcpy(nxt[clone],nxt[q],sizeof(nxt[q]));fail[clone]=fail[q];fail[cur]=fail[q]=clone;while(p&&nxt[p][c]==q)nxt[p][c]=clone,p=fail[p];return ;
}
int ncnt,rt[MAXN+5],ch[25*MAXN+5][2];
void Insert(int &u,int L,int R,int p){
    u=++ncnt;if(L==R)return ;int Mid=(L+R)>>1;if(p<=Mid)Insert(ch[u][0],L,Mid,p);else Insert(ch[u][1],Mid+1,R,p);return ;
}
int Merge(int u,int v){
    if(!u||!v) return u|v;int p=++ncnt;ch[p][0]=Merge(ch[u][0],ch[v][0]);ch[p][1]=Merge(ch[u][1],ch[v][1]);return p;
}
int n;
vector<int> G[MAXN+5];
void DFS(int u){
    if(ed[u])Insert(rt[u],1,n,ed[u]);for(int i=0;i<(int)G[u].size();i++){
    int v=G[u][i];DFS(v);rt[u]=Merge(rt[u],rt[v]);}return ;
}
int ans,f[MAXN+5],fa[MAXN+5];
bool Query(int u,int L,int R,int qL,int qR){
    if(!u) return 0;if(qL<=L&&R<=qR)return 1;int Mid=(L+R)>>1;if(qL<=Mid)if(Query(ch[u][0],L,Mid,qL,qR))return 1;if(Mid+1<=qR)if(Query(ch[u][1],Mid+1,R,qL,qR))return 1;return 0;
}
void DP(int u){
    for(int i=0;i<(int)G[u].size();i++){
    int v=G[u][i];if(u==Root)f[v]=1,fa[v]=v;else{
    if(Query(rt[fa[u]],1,n,ed[v]-maxlen[v]+maxlen[fa[u]],ed[v]-1))f[v]=f[fa[u]]+1,fa[v]=v;else f[v]=f[fa[u]],fa[v]=fa[u];}ans=max(ans,f[v]);DP(v);}return ;
}
char S[MAXN+5];
int main(){
    n=read();scanf("%s",S+1);Init();for(int i=1;i<=n;i++)Extend(S[i]-'a'+1,i);for(int i=2;i<=scnt;i++)G[fail[i]].push_back(i);DFS(Root);DP(Root);printf("%d\n",ans);return 0;
}