洛谷P5284 [十二省联考2019]字符串问题（SAM+倍增+最长路）

朴灿烈づ我的快乐病毒、 2021-12-23 05:45 180阅读 0赞

## 题面 ##

[传送门][Link 1]

## 题解 ##

首先，我们把串反过来，那么前缀就变成后缀，建一个\\(SAM\\)。我们发现一个节点的后缀是它的所有祖先

那么我们是不是直接按着\\(parent\\)树建边就可以了呢？

显然不是。我们假设在\\(SAM\\)的某个节点上同时存在某个\\(a\_i\\)和\\(b\_j\\)且\\(|b\_j|>|a\_i|\\)，\\(b\_j\\)不是\\(a\_i\\)的后缀，但它们仍然有边相连！（自己到自己就当有边吧……）

对于每一个节点，我们把处于这个节点中的所有串排个序，按长度为第一关键字，是否是\\(B\\)串为第二关键字。每个\\(B\\)串向最短的比它长的\\(B\\)串（记为\\(S\\)）连边，并向所有比\\(S\\)短比自己长的\\(A\\)串连边。容易发现这样的边数是\\(O(n)\\)的

最后得到的图如果不是\\(DAG\\)无解，否则跑个最长路就可以了

//minamoto #include<bits/stdc++.h> #define inline __attribute__((always_inline)) #define R register #define ll long long #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } int read(char *s){ R int len=0;R char ch;while(((ch=getc())>'z'||ch<'a')); for(s[++len]=ch;(ch=getc())>='a'&&ch<='z';s[++len]=ch); return s[len+1]='\0',len; } const int N=1e6+5; struct eg{int v,nx;}e[N];int head[N],deg[N],tot; inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot,++deg[v];} int lst[N],ga[N][25],fa[N],l[N],pos[N],ch[N][26],cnt=1,las=1; int n,lg,na,nb;char s[N];vector<int>g[N]; int A[N],B[N],st[N],len[N],top; inline int newnode(R int len){return ++cnt,l[cnt]=len,memset(ch[cnt],0,104),cnt;} inline int newnode(R int len,R int p){return ++cnt,l[cnt]=len,memcpy(ch[cnt],ch[p],104),cnt;} bool cmp(const int &x,const int &y){return len[x]==len[y]?st[x]<st[y]:len[x]<len[y];} void ins(int c){ int p=las,np=las=newnode(l[p]+1); for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np; if(!p)fa[np]=1; else{ int q=ch[p][c]; if(l[q]==l[p]+1)fa[np]=q; else{ int nq=newnode(l[p]+1,q); fa[nq]=fa[q],fa[q]=fa[np]=nq; for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq; } } } void Add(int p,int L,int is){ fd(i,lg,0)if(l[ga[p][i]]>=L)p=ga[p][i]; st[++top]=is,len[top]=L,g[p].push_back(top); } ll dis[N];int q[N],h,t; ll topo(){ ll res=0;h=1,t=0; fp(i,1,top){ if(!deg[i])q[++t]=i; if(!st[i])len[i]=0; } while(h<=t){ int u=q[h++];cmax(res,dis[u]+len[u]); go(u){ cmax(dis[v],dis[u]+len[u]); if(!--deg[v])q[++t]=v; } } fp(i,1,top)if(deg[i])return -1; return res; } void clr(){ memset(st,0,(top+1)<<2); memset(deg,0,(top+1)<<2); memset(head,0,(top+1)<<2); memset(dis,0,(top+1)<<3); } int main(){ // freopen("testdata.in","r",stdin); for(int T=read();T;--T){ n=read(s),cnt=0,las=newnode(0),tot=0; fd(i,n,1)ins(s[i]-'a'),pos[i]=las; lg=log2(cnt)+1; fp(i,1,cnt)ga[i][0]=fa[i]; fp(j,1,lg)fp(i,1,cnt)ga[i][j]=ga[ga[i][j-1]][j-1]; fp(i,1,cnt)g[i].clear(); top=cnt,na=read(); for(R int i=1,l,r;i<=na;++i)l=read(),r=read(),Add(pos[l],r-l+1,1),A[i]=top; nb=read(); for(R int i=1,l,r;i<=nb;++i)l=read(),r=read(),Add(pos[l],r-l+1,0),B[i]=top; fp(i,1,cnt)sort(g[i].begin(),g[i].end(),cmp); for(R int i=1,now;i<=cnt;++i){ now=i; fp(j,0,g[i].size()-1){ add(now,g[i][j]); if(!st[g[i][j]])now=g[i][j]; } lst[i]=now; } fp(i,2,cnt)add(lst[fa[i]],i); for(R int x,y,i=read();i;--i)x=read(),y=read(),add(A[x],B[y]); printf("%lld\n",topo()); clr(); } return 0; }

转载于:https://www.cnblogs.com/bztMinamoto/p/10684233.html

[Link 1]: https://www.luogu.org/problemnew/show/P5284