题目大意:

给定两个字符串,存在三种操作,分别是在a,b串末尾加一个字符串,和询问两串的LCS

 

题解:

Get新套路:把两串建在同一SAM上,将重合的位置合并为同一节点,再加个标记数组,如果两者的LCS标记都存在那么就直接更新答案.

注意标记需要沿father上传,每新建一个节点就打上标记并更新祖先

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #define RG register 8 using namespace std; 9 const int N=5000005,M=10000005;10 char S[N];int ch[M][3],fa[M],cur=1,cnt=1,ans=0,n=0,s[2][N],m=0,dis[M],pre[2][N],l[N];11 int mark[M];long long ret=0;12 void updata(int p){13 while(fa[p] && (mark[p]&mark[fa[p]])!=mark[p]){14 if(mark[p]==3)ans=max(ans,dis[p]);15 mark[fa[p]]|=mark[p];16 p=fa[p];17 }18 if(mark[p]==3)ans=max(ans,dis[p]);19 }20 int build(int last,int k,int c)21 {22 cur=++cnt;dis[cur]=dis[last]+1;23 RG int p=last;24 for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;25 if(!p)fa[cur]=1;26 else{27 int q=ch[p][c];28 if(dis[q]==dis[p]+1)fa[cur]=q;29 else{30 int nt=++cnt;dis[nt]=dis[p]+1;31 memcpy(ch[nt],ch[q],sizeof(ch[q]));32 fa[nt]=fa[q];fa[q]=fa[cur]=nt;33 updata(q); /*不能忘记这个地方*/34 for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;35 }36 }37 mark[cur]|=(1<
           
            >1)%2;fg1++;49 s[fg0][++l[fg0]]=fg1;50 if(pre[fg0][l[fg0]-1]==pre[fg0^1][l[fg0]-1] && fg1==s[fg0^1][l[fg0]]){51 pre[fg0][l[fg0]]=pre[fg0^1][l[fg0]];52 mark[pre[fg0][l[fg0]]]|=(1<