[关闭]
@xzyxzy 2018-07-02T10:12:29.000000Z 字数 6122 阅读 1031

广义后缀自动机

字符串 题解

作业部落

评论地址


一、前言

广义后缀自动机实际上考得比普通后缀自动机要更多更灵活
所以这里作为一个小专题呈现,题单在后缀自动机的总题单里
为了更好掌握广义,这里提供一个高级模板题的题解

二、构建方法

普通后缀自动机处理单串的问题,多串就只能使用广义

最方便的构建

一种方案是把字符串中间依次用从未出现过的字符连接,当作一个字符串处理,再多几个特判

  1. for(int i=1;i<=m;i++)
  2. {
  3. string A; cin>>A; s[++l]='#';
  4. for(int j=0,l=A.size();j<l;j++) s[++l]=A[j];
  5. }

一种方案是每插入一个串就把,其余什么都不用改变

  1. for(int i=1;i<=m;i++)
  2. {
  3. lst=1; cin>>s; l=s.size();
  4. for(int j=0;j<l;j++) Extend(s[j]-'0');
  5. }

最准确的构建

其实准确来说,广义后缀自动机是通过遍历Trie树建的,所以要先建好
每次找到的节点作为往后接即可

有两种方法:遍历建后缀自动机
叶大佬告诉我们,会被卡成不会,就像下面图片中的例子PKUSC买了个草稿本~

  1. int Extend(int f,int c)
  2. {
  3. if(ch[f][c]&&len[ch[f][c]]==len[f]+1) return ch[f][c];//?!
  4. int p=++node,ff=0;lst=p;
  5. len[p]=len[f]+1;
  6. while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
  7. if(!f) {fa[p]=1;return p;}
  8. int x=ch[f][c],y=++node;
  9. if(len[x]==len[f]+1) {fa[p]=x;node--;return p;}
  10. if(len[p]==len[f]+1) ff=1;//?!
  11. memcpy(ch[y],ch[x],sizeof(ch[y]));
  12. len[y]=len[f]+1; fa[y]=fa[x]; fa[x]=fa[p]=y;
  13. while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];//原因就在这
  14. return ff?y:p;
  15. }

你会发现这和后缀自动机的模板有些区别诶
首先是有一个返回值,这个很好理解,返回的是如果下次要往后接的,也就是方便找到树某点在上的位置,直接传进来就好啦
然后是有一个if(len[p]==len[f]+1) return y;的特判
前面也有一个if(ch[f][c]&&len[ch[f][c]]==len[f]+1) return ch[f][c];的特判

好,广义的构建就讲完了
什么?!WTF?!那个特判是啥意思我还不造嘞!
别急,我们来通过例题理解它

三、例题

链接HN省队集训
题意:给个字符串,强制在线进行个操作,询问/串长
PFyaKH.png
题解
对于操作
记录表示在第次操作后号串的结尾字符在上的节点编号是,当在第次操作在字符串后插入字符时,令,然后照常插入即可

对于操作
记录表示在号点,由号字符串贡献的集合的大小,实际意义就是号点代表的字符串集合在个串中共出现了,其中在号串中出现了次。
查询串中串的出现次数,那么串在次操作后的结尾位置是,那么就是答案。
这里的是在树上对子树进行求和才有上述意义,原理可见于我的另一篇博文后缀自动机,但是这里需要在线插入节点,于是我们用维护树上的,每次断开或者连上父亲的时候相当是给节点到根的路径,所以这里的只需要支持链加,不需要改变树的根所以没有等操作,如果需要学习,可见我的另一篇博文lct

对于操作
维护一个全局变量,每个节点贡献的本质不同的子串个数就是

对于操作
上匹配到T的结束位置的节点,

复杂度分析
操作的总复杂度是的,操作的,操作,操作的,都是的复杂度
所以总共时间复杂度是
空间复杂度左右

代码如下

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #define ll long long
  6. using namespace std;
  7. int read()
  8. {
  9. char ch=getchar();int h=0,t=1;
  10. while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
  11. if(ch=='-') t=-1,ch=getchar();
  12. while(ch>='0'&&ch<='9') h=h*10+ch-'0',ch=getchar();
  13. return h*t;
  14. }
  15. const int N=1e6+100;
  16. char s[N];
  17. int n,zx,m,ans,node=1;
  18. int fa[N],ch[N][11],len[N],pos[N][21];
  19. ll sum;
  20. namespace lct
  21. {
  22. #define lc t[x].ch[0]
  23. #define rc t[x].ch[1]
  24. struct LCT{int fa,ch[2],val[21],tag[21];}t[N];
  25. int isrt(int x) {return t[t[x].fa].ch[0]!=x&&t[t[x].fa].ch[1]!=x;}
  26. void Tag(int x,int y,int k) {t[x].val[y]+=k; t[x].tag[y]+=k;}
  27. void pushdown(int x)
  28. {
  29. for(int i=1;i<=n;i++)
  30. {
  31. if(!t[x].tag[i]) continue;
  32. if(lc) Tag(lc,i,t[x].tag[i]);
  33. if(rc) Tag(rc,i,t[x].tag[i]);
  34. t[x].tag[i]=0;
  35. }
  36. }
  37. void rotate(int x)
  38. {
  39. int y=t[x].fa,z=t[y].fa;
  40. int k=t[y].ch[1]==x;
  41. if(!isrt(y)) t[z].ch[t[z].ch[1]==y]=x; t[x].fa=z;
  42. t[y].ch[k]=t[x].ch[k^1]; t[t[x].ch[k^1]].fa=y;
  43. t[x].ch[k^1]=y; t[y].fa=x;
  44. }
  45. void Push(int x){if(!isrt(x)) Push(t[x].fa);pushdown(x);}
  46. void splay(int x)
  47. {
  48. Push(x);
  49. while(!isrt(x))
  50. {
  51. int y=t[x].fa,z=t[y].fa;
  52. if(!isrt(y)) (t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);
  53. rotate(x);
  54. }
  55. }
  56. void Access(int x) {for(int y=0;x;y=x,x=t[x].fa) splay(x),rc=y;}
  57. void Add(int x,int y,int op) {for(int i=1;i<=n;i++) Tag(x,i,t[y].val[i]*op);}
  58. void link(int x,int y) {Push(x);t[x].fa=y;Access(y);splay(y);Add(y,x,1);}
  59. void cut(int x) {Access(x);splay(x);Add(lc,x,-1);lc=t[lc].fa=0;}
  60. int query(int x,int k) {Push(x);return t[x].val[k];}
  61. }
  62. int Extend(int f,int id,int c)
  63. {
  64. if(ch[f][c]&&len[ch[f][c]]==len[f]+1)
  65. {
  66. int p=ch[f][c];
  67. lct::Access(p);lct::splay(p);lct::Tag(p,id,1);
  68. return p;
  69. }
  70. int p=++node; len[p]=len[f]+1; lct::t[p].val[id]=1;
  71. while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
  72. if(!f) {fa[p]=1;lct::link(p,1);sum+=len[p]-len[fa[p]];return p;}
  73. int x=ch[f][c];
  74. if(len[f]+1==len[x]) {fa[p]=x;lct::link(p,x);sum+=len[p]-len[fa[p]];return p;}
  75. if(len[f]+1==len[p])//!!
  76. {
  77. lct::cut(x);lct::link(p,fa[x]);lct::link(x,p);
  78. memcpy(ch[p],ch[x],sizeof(ch[p]));
  79. fa[p]=fa[x]; fa[x]=p;
  80. sum-=len[p]-len[fa[p]];
  81. while(f&&ch[f][c]==x) ch[f][c]=p,f=fa[f];
  82. }
  83. else
  84. {
  85. int y=++node; len[y]=len[f]+1;
  86. lct::cut(x);lct::link(y,fa[x]);lct::link(x,y);lct::link(p,y);
  87. memcpy(ch[y],ch[x],sizeof(ch[y]));
  88. fa[y]=fa[x]; fa[x]=fa[p]=y;
  89. while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
  90. }
  91. sum+=len[p]-len[fa[p]];
  92. return p;
  93. }
  94. int calc()
  95. {
  96. int x=1,res=0,i,l; scanf("%s",s+1);
  97. for(i=1,l=strlen(s+1);i<=l&&x;i++) x=ch[x][s[i]-'0'];
  98. if(i!=l+1) return 0;
  99. lct::Push(x);
  100. for(i=1;i<=n;i++) res=max(res,lct::t[x].val[i]);
  101. return res;
  102. }
  103. int main()
  104. {
  105. n=read();zx=read();
  106. for(int i=1;i<=n;i++)
  107. {
  108. scanf("%s",s+1); pos[0][i]=1;
  109. for(int p=1,l=strlen(s+1);p<=l;p++)
  110. pos[0][i]=Extend(pos[0][i],i,s[p]-'0');
  111. }
  112. m=read();
  113. for(int i=1;i<=m;i++)
  114. {
  115. int op=read(),x,y,z;
  116. for(int p=1;p<=n;p++) pos[i][p]=pos[i-1][p];
  117. if(op<=2) x=read(),y=read();
  118. if(op==1) y=(y^(ans*zx))%10,pos[i][x]=Extend(pos[i][x],x,y);
  119. else if(op==2) z=read(),printf("%d\n",ans=lct::query(pos[y][x],z));
  120. else if(op==3) printf("%lld\n",sum);
  121. else printf("%d\n",ans=calc());
  122. }
  123. return 0;
  124. }

Wait!
出题人和我讲这道题的时候,特别强调要特判!
但是我一直不理解,把特判if(len[f]+1==len[p]) ff=1;删了后还是过了本题
于是他给了一组并且在加强了数据

  1. Input
  2. 2 0
  3. 3201
  4. 01
  5. 1
  6. 2 2 0 1
  7. Output
  8. Right : 1
  9. Wrong : 0

首先我们建出第一个串的(黑边是上的边,基佬紫边是树上的边)
PF65OH.jpg
我们先加特判,那么继续建就会这样(姨妈红边是删去的边)
PF646e.jpg
继续加边
PF6T0A.jpg
但是如果不加这个特判,就会撒夫夫地把蓝给复制一边,但是这时第二个串的的结尾位置是,当我查询串在串中出现次数就会访问到,此时很遗憾地发现调用到了节点,它没有记录蓝的信息
PF6omd.jpg
这样写代码很长,有没有一种简单的写法捏?
有的,我们发现黑不会再被访问到,相当于他的贡献被算到了六号点上,同时又没有点指向它所以它不会被访问到。对比上面两张图,我们发现其实就是中的黑中的黑是完全一样的诶!
于是直接返回黑就好啦
把上述代码的改成下面这种

  1. int Extend(int f,int id,int c)
  2. {
  3. if(ch[f][c]&&len[ch[f][c]]==len[f]+1)
  4. {
  5. int p=ch[f][c];
  6. lct::Access(p);lct::splay(p);lct::Tag(p,id,1);
  7. return p;
  8. }
  9. int p=++node,ff=0; len[p]=len[f]+1; lct::t[p].val[id]=1;
  10. while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
  11. if(!f) {fa[p]=1;lct::link(p,1);sum+=len[p]-len[fa[p]];return p;}
  12. int x=ch[f][c];
  13. if(len[f]+1==len[x]) {fa[p]=x;lct::link(p,x);sum+=len[p]-len[fa[p]];return p;}
  14. if(len[f]+1==len[p]) ff=1;
  15. int y=++node; len[y]=len[f]+1;
  16. lct::cut(x);lct::link(y,fa[x]);lct::link(x,y);lct::link(p,y);
  17. memcpy(ch[y],ch[x],sizeof(ch[y]));
  18. fa[y]=fa[x]; fa[x]=fa[p]=y;
  19. while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
  20. sum+=len[p]-len[fa[p]];
  21. return ff?y:p;
  22. }

是不是很方便?

从本质上分析这两个特判

  1. if(ch[f][c]&&len[ch[f][c]]==len[f]+1) return ch[f][c];

我们建是在树上遍历建的,这句话表示访问到树上一个点,它在上已经被建出来了,所以不需要新建

  1. if(len[f]+1==len[p]) ff=1;

这句特判起作用的条件是中间没有被改变,也就是说存在,假设表示的字符串是,那么插入字符后产生,但是已经存在于自动机上,所以要把它从原来的状态剥离出来,复制一遍,从后来的操作中可以发现最后我们需要的也就是的点应该是复制出来的那个点

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注