【CF700E】Cool Slogans 后缀自动机+线段树合并
合并 线段 后缀 自动机
2023-09-11 14:15:24 时间
【CF700E】Cool Slogans
题意:给你一个字符串S,求一个最长的字符串序列$s_1,s_2,...,s_k$,满足$\forall s_i$是S的子串,且$s_i$在$s_{i-1}$里出现了2次。
$|S|\le 10^5$
题解:容易想到pre树的性质。定义一个字符串的tail为它的出现次数>=2的最长的后缀。对于结束节点来说,它的tail就是它的pre。但是对于一般的点,我们需要不断沿着pre向上找,找到第一个在原串出现2次的节点才能得到tail。具体做法是,我们可以记录spre[i]表示最上面一个没有在i中出现两次的点,f[i]代表从沿着spre走到根的路径长度(spre[i]也是最上面一个f不变的点)。那么,如果i包含sp[pre[i]],则sp[i]=i,f[i]=f[pre[i]]+1;否则sp[i]=sp[pre[i]],f[i]=f[pre[i]]。
那么如何检查串a是否在串b中出现2次呢?可以用线段树维护right集合,如果串a在指定范围内出现过,则说明a在b中出现了2次。如何维护right集合呢?线段树合并即可。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn=400010; int n,tot,Cnt,cnt,last,ans; int ch[maxn][26],pre[maxn],mx[maxn],to[maxn],nxt[maxn],head[maxn],f[maxn],pos[maxn],rt[maxn],val[maxn],sf[maxn]; struct sag { int ls,rs; }s[maxn*50]; char str[maxn]; inline void extend(int x) { int np=++Cnt,p=last; mx[np]=mx[p]+1,last=np; for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=np; if(!p) pre[np]=1; else { int q=ch[p][x]; if(mx[q]==mx[p]+1) pre[np]=q; else { int nq=++Cnt; mx[nq]=mx[p]+1,pre[nq]=pre[q],pre[np]=pre[q]=nq; memcpy(ch[nq],ch[q],sizeof(ch[q])); for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=nq; } } } inline void add(int a,int b) { to[cnt]=b,nxt[cnt]=head[a],head[a]=cnt++; } void insert(int l,int r,int &x,int a) { x=++tot; if(l==r) return ; int mid=(l+r)>>1; if(a<=mid) insert(l,mid,s[x].ls,a); else insert(mid+1,r,s[x].rs,a); } int merge(int a,int b) { if(!a||!b) return a^b; int c=++tot; s[c].ls=merge(s[a].ls,s[b].ls),s[c].rs=merge(s[a].rs,s[b].rs); return c; } bool count(int l,int r,int x,int a,int b) { if(!x) return 0; if(a<=l&&r<=b) return 1; int mid=(l+r)>>1; if(b<=mid) return count(l,mid,s[x].ls,a,b); if(a>mid) return count(mid+1,r,s[x].rs,a,b); return count(l,mid,s[x].ls,a,b)|count(mid+1,r,s[x].rs,a,b); } void dfs1(int x) { int i; for(i=head[x];i!=-1;i=nxt[i]) dfs1(to[i]),pos[x]=pos[to[i]],rt[x]=merge(rt[x],rt[to[i]]); } void dfs2(int x) { ans=max(ans,f[x]); int i; for(i=head[x];i!=-1;i=nxt[i]) { int ct=count(0,n-1,rt[sf[x]],pos[to[i]]+mx[sf[x]]-mx[to[i]],pos[to[i]]-1); if(ct) f[to[i]]=f[x]+1,sf[to[i]]=to[i]; else f[to[i]]=f[x],sf[to[i]]=sf[x]; dfs2(to[i]); } } int main() { //freopen("cf700E.in","r",stdin); scanf("%d%s",&n,str); int i; Cnt=last=1; memset(head,-1,sizeof(head)); for(i=0;i<n;i++) extend(str[i]-'a'),pos[last]=i,insert(0,n-1,rt[last],i); for(i=2;i<=Cnt;i++) add(pre[i],i); dfs1(1); for(i=head[1];i!=-1;i=nxt[i]) f[to[i]]=1,sf[to[i]]=to[i],dfs2(to[i]); printf("%d",ans); return 0; }
相关文章
- Google Earth Engine——TRMM/34B2产品包含一个网格化的、经TRMM调整的、合并的红外降水(毫米/小时)和降水误差的有效值估计,时间分辨率为3小时,空间分辨率为0.25度。
- 【BZOJ4919】[Lydsy六月月赛]大根堆 线段树合并
- ArcGIS 相同要素类的多Shp文件或多要素合并
- Swift - 使用位运算提取颜色,合并颜色
- Hive合并小文件的配置项
- 【LeetCode-面试算法经典-Java实现】【056-Merge Intervals(区间合并)】
- 如何将多张CAD图纸合并成一个图纸文件?
- 【codeforces666E】Forensic Examination 广义后缀自动机+树上倍增+线段树合并
- 【bzoj2653】middle 可持久化线段树区间合并
- 【bzoj1018】[SHOI2008]堵塞的交通traffic 线段树区间合并+STL-set
- 【bzoj3747】[POI2015]Kinoman 线段树区间合并
- 【bzoj4719】[Noip2016]天天爱跑步 权值线段树合并
- 【bzoj2212】[Poi2011]Tree Rotations 权值线段树合并
- SQL server 字段合并CAST(org_no AS VARCHAR(20))+CAST(page_no AS VARCHAR(20))+CAST(djlb_no AS VARCHAR(20)))