题目大意:
给定两个字符串,存在三种操作,分别是在a,b串末尾加一个字符串,和询问两串的LCS
题解:
Get新套路:把两串建在同一SAM上,将重合的位置合并为同一节点,再加个标记数组,如果两者的LCS标记都存在那么就直接更新答案.
注意标记需要沿father上传,每新建一个节点就打上标记并更新祖先
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
using namespace std;
const int N=,M=;
char S[N];int ch[M][],fa[M],cur=,cnt=,ans=,n=,s[][N],m=,dis[M],pre[][N],l[N];
int mark[M];long long ret=;
void updata(int p){
while(fa[p] && (mark[p]&mark[fa[p]])!=mark[p]){
if(mark[p]==)ans=max(ans,dis[p]);
mark[fa[p]]|=mark[p];
p=fa[p];
}
if(mark[p]==)ans=max(ans,dis[p]);
}
int build(int last,int k,int c)
{
cur=++cnt;dis[cur]=dis[last]+;
RG int p=last;
for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;
if(!p)fa[cur]=;
else{
int q=ch[p][c];
if(dis[q]==dis[p]+)fa[cur]=q;
else{
int nt=++cnt;dis[nt]=dis[p]+;
memcpy(ch[nt],ch[q],sizeof(ch[q]));
fa[nt]=fa[q];fa[q]=fa[cur]=nt;
updata(q); /*不能忘记这个地方*/
for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;
}
}
mark[cur]|=(<<k);
updata(cur);
return cur;
}
void work()
{
int Q,fg0,fg1;
scanf("%d",&Q);scanf("%s",S+);
pre[][]=pre[][]=;
for(int i=,x;i<=Q;i++){
x=S[i]-'';
fg0=(x^ans)%;fg1=((x^ans)>>)%;fg1++;
s[fg0][++l[fg0]]=fg1;
if(pre[fg0][l[fg0]-]==pre[fg0^][l[fg0]-] && fg1==s[fg0^][l[fg0]]){
pre[fg0][l[fg0]]=pre[fg0^][l[fg0]];
mark[pre[fg0][l[fg0]]]|=(<<fg0);
updata(pre[fg0][l[fg0]]);
}
else{
pre[fg0][l[fg0]]=build(pre[fg0][l[fg0]-],fg0,fg1);
}
ret+=ans;
}
printf("%lld\n",ret);
}
int main()
{
freopen("lcs.in","r",stdin);
freopen("lcs.out","w",stdout);
work();
return ;
}