解析

好題。
首先，我們每次都令 $s_i$ 是 $s_{i+1}$ 的后綴，肯定是不劣的
問題就可以轉化到 fail 樹上了
首先肯定要線段樹合并處理出endpos集合
樸素想法：設父親 $fa$ 的結束位置為 $po{s}_{fa}$，若 $[po{s}_{fa}?le{n}_{fa}+1,po{s}_{fa}]$ 中有兩個兒子 $s$，就令 $an{s}_{fa}+1\to an{s}_s$。
但是仔細想想還會有一些問題
比如，可能會跳兩次才可以轉移，但是連續的父子之間都無法構成二倍關系。這個不麻煩，記錄一下上一次成功轉移的 $pre$，每次判斷 $[po{s}_{pre}?le{n}_{pre}+1,po{s}_{pre}]$ 即可

還有一個問題，我們這里的 $len$ 都是最長長度，會不會有一個同一等價類里較短的子串可以轉移，而那個最長子串無法轉移呢？
不會
考慮反證證明：
假設有子串：

A

cA

AA
其中1、2屬于同一等價類，2無法轉移到3而1可以
那么必然有串：cAA（這樣12才能是一個等價類）
又由于3是該等價類最長字符串，所以AA和cAA不屬于同一等價類
也就是說有一個位置出現了AA卻沒有出現cAA，那么這個地方（第一個A的位置）也會出現了A卻沒有出現cA
所以1、2不在一個等價類里，與題設矛盾，原命題得證

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=4e5+100; const int mod=1e9+7; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } int n,m;int ed[N]; struct SAM{struct node{int len,fa;int tr[26];}st[N];int lst=1,tot=1;int pl[N];inline void ins(int c,int o){c-='a';int cur=++tot,p=lst;lst=tot;ed[cur]=o;st[cur].len=st[p].len+1;for(;p&&!st[p].tr[c];p=st[p].fa) st[p].tr[c]=cur;if(!st[p].tr[c]) st[cur].fa=1;else{int q=st[p].tr[c];if(st[q].len==st[p].len+1) st[cur].fa=q;else{int pp=++tot;st[pp]=st[q];ed[pp]=ed[q];st[pp].len=st[p].len+1;st[cur].fa=st[q].fa=pp;for(;p&&st[p].tr[c]==q;p=st[p].fa) st[p].tr[c]=pp;}}}void print(){for(int i=1;i<=tot;i++){printf("i=%d fa=%d len=%d ed=%d\n",i,st[i].fa,st[i].len,ed[i]);}putchar('\n');return;} }s;struct segmentTree{#define mid ((l+r)>>1)struct tree{int ls,rs,siz;}tr[N<<6];int rt[N],tot;inline int copy(int x){tr[++tot]=tr[x];return tot;}inline void pushup(int k){tr[k].siz=tr[tr[k].ls].siz+tr[tr[k].rs].siz;return;}void add(int &k,int l,int r,int p){if(!k) k=copy(0);if(l==r){tr[k].siz++;return;}if(p<=mid) add(tr[k].ls,l,mid,p);else add(tr[k].rs,mid+1,r,p);pushup(k);}int merge(int a,int b,int l,int r){if(!a||!b) return a|b;a=copy(a);if(l==r){tr[a].siz+=tr[b].siz;return a;}tr[a].ls=merge(tr[a].ls,tr[b].ls,l,mid);tr[a].rs=merge(tr[a].rs,tr[b].rs,mid+1,r);pushup(a);return a;}int ask(int k,int l,int r,int x,int y){if(x>y) return 0;if(!k) return 0;if(x<=l&&r<=y) return tr[k].siz;int res(0);if(x<=mid) res+=ask(tr[k].ls,l,mid,x,y);if(y>mid) res+=ask(tr[k].rs,mid+1,r,x,y);return res;} }t;char ss[N];vector<int>v[N]; int dp[N],pre[N]; void dfs1(int x){if(ed[x]) t.add(t.rt[x],1,n,ed[x]);for(int to:v[x]){//printf("%d -> %d\n",x,to);dfs1(to);t.rt[x]=t.merge(t.rt[x],t.rt[to],1,n);}return; } int ans; void dfs2(int x){//printf("x=%d dp=%d pre=%d\n",x,dp[x],pre[x]);ans=max(ans,dp[x]);for(int to:v[x]){//printf(" %d -> %d +1? (%d %d)\n",x,to,ed[to]-s.st[to].len+s.st[pre[x]].len,ed[to]-1);if(x==1||(ed[to]&&t.ask(t.rt[pre[x]],1,n,ed[to]-s.st[to].len+s.st[pre[x]].len,ed[to]-1))){dp[to]=dp[x]+1;pre[to]=to;}else dp[to]=dp[x],pre[to]=pre[x];dfs2(to);}return; } signed main() { #ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout); #endif //printf("%d\n",sizeof(t)/1024/1024);n=read();scanf(" %s",ss+1);for(int i=1;i<=n;i++) s.ins(ss[i],i);//s.print();for(int i=2;i<=s.tot;i++) v[s.st[i].fa].push_back(i);dfs1(1);dfs2(1);printf("%d\n",ans);return 0; } /* 21 abcaaaaabbcbacbabcbcb*/

總結

以上是生活随笔為你收集整理的CF700E Cool Slogans（SAM，dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。