[关闭]
@Scarlet 2017-03-14T08:50:42.000000Z 字数 4154 阅读 465

字符串算法

挖新坑!

字符串

字符串上的算法是抽象数据结构的极致,以SAM、PAM为代表的脑子进水高超数据结构深得出题人心。按照CF上AC人数排序翻译记录


126B[KMP]

题意:找到一个前缀,它既是后缀,也在中间出现过

考虑KMP的性质:的后缀,那么也是的后缀。看中间有没有出现某个前缀只需要看和前缀长度的大小关系

514C[hash]

题意:询问一个串能否通过修改一个字符变为给定集合中的串,
枚举改什么,蛤希

471D[KMP]

题意:见原题图
差分后KMP,比T1还要裸。

535D[KMP]

题意:已知长为的串匹配有给定的个起点,求原串方案数

432D[KMP]

题意:求前缀等于后缀的各长度的子串数量
同126B

633C[AC自动机]

题意:给出一篇小写字母、翻转单词、去掉空格的文章和词典,求原串
AC自动机上ALB,每次到一个点就DP一下

631D[KMP]

题意:给你两个个压缩后的字符串,求匹配起点数
去掉模式串首尾后kmp,放到另一串中判断

128B[SAM]

题意:第大子串
先建一个sam,然后在上面DP就好了。
还看到有很多小哥把每个后缀放入堆中依次取出的做法,感觉强无敌。

526D[KMP]

题意:输出每个前缀是否能被表示为ABABABA的形状
在nxt上螺杆就好了吧

427D[]

题意:最长公共子串

149E[KMP]

题意:给定一个字符串,接下来有个字符串,对于每个字符串,判断是否存在
正反两遍kmp,记录一下匹配最远的位置

557E[]

题意:找出的子串中字典序第小的“半回文串”,给出半回文串定义是:对于任意

441D[]

题意:输出字典序最小的两两元素交换方案,使交换后的排列最少交换次可以变成

533F[]

题目太长不敢翻译
题意:

235C[]

题意:给原串,和若干个询问串。求原串里有多少个不同子串可以通过询问串循环移动得到。

756D[]

太长不敢翻译
题意:

19C[]

没看懂

504E[hash]

题意:树链上子串求LCP
树剖后二分+hash

领悟了后缀数组后突然发现所有匹配问题都变成了数数题...

来源未知:Koishi Loves String

题意:支持在前后加字符,前后加字符,询问内的匹配数,允许离线
第一眼感觉是不可做题。
qlj提醒我一下可以对整个串建个sam...
然后我怎么就轻易地发现是一道SB题...?

先把模型对应到整个串上:一个字符串,问中的匹配数
先把模型对应到后缀树上:子串一定是后缀树上的一条链,那么就便成求子树内有多少后缀对应的点在中。
因为后缀树一定是静态的,所以题目也一定可以变成序列上询问区间中有多少点值在中,这个大家都会差分离线+BIT。
再把模型对应到后缀树组上:子串包含的子树就变成了sa上的一段连续区间使得这些后缀和后缀不小于,按照height排序后并查集完全可以胜任。
既然能找到区间,到这里,问题就十分simple了。
复杂度

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define N 1000010
  6. #define clr(a) memset(a,0,sizeof(a))
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. inline LL read()
  11. {
  12. LL x=0,f=1;char G;
  13. while(c>57||c<48){if(c=='-')f=-1;G;}
  14. while(c>47&&c<58)x=x*10+c-48,G;
  15. return x*f;
  16. }
  17. //SAM
  18. int n,O,p,q,np,nq,i,j,k,t,P,S[N],R[N],C[N][27],c[N][27],F[N],L[N],T[N],h[N];char s[N],r[N];bool v[N];
  19. void A(int w)
  20. {
  21. for(p=np,L[np=++O]=L[p]+1,T[np]=i;p&&!c[p][w];p=F[p])c[p][w]=np;
  22. if(!p)F[np]=1;else if(L[q=c[p][w]]==L[p]+1)F[np]=q;else for(L[nq=++O]=L[p]+1,memcpy(c[nq],c[q],sizeof(c[q])),F[nq]=F[q],F[q]=F[np]=nq;p&&c[p][w]==q;p=F[p])c[p][w]=nq;
  23. }
  24. void dfs(int x)
  25. {
  26. if(T[x])S[++t]=T[x];
  27. for(int i=0;i<=26;i++)if(C[x][i])dfs(C[x][i]);
  28. }
  29. bool cmph(int x,int y){return h[x]>h[y];}
  30. //BIT
  31. int cc[N];
  32. void add(int x){for(x++;x<N;x+=x&-x)cc[x]++;}
  33. int ask(int x){if(x<0)return 0;int ret=0;for(x++;x;x-=x&-x)ret+=cc[x];return ret;}
  34. //dsu
  35. int f[N],ff[N],ll[N];
  36. int fd(int x){return x==f[x]?x:f[x]=fd(f[x]);}
  37. //Offline 1
  38. int as;
  39. struct Ask{int a,b,c,d,i;}E[N];
  40. bool cmpA(Ask x,Ask y){return x.d>y.d;}
  41. //Offline 2
  42. int ans[N],tot;
  43. struct poi{int a,b,c,i,_;}Q[2*N];
  44. bool cmpQ(poi x,poi y){return x.a<y.a;}
  45. //Inition
  46. char Sf[N],Sb[N],Tf[N],Tb[N];
  47. int sf,sb,tf,tb;
  48. void work()
  49. {
  50. //build SAM
  51. n=strlen(s+1);
  52. O=p=q=np=nq=k=t=P=0;
  53. clr(S),clr(R),clr(C),clr(c),clr(F),clr(L),clr(T),clr(h),clr(v);
  54. for(np=++O,i=n;i;i--)A(s[i]-'a');
  55. for(v[1]=i=1;i<=O;i++)if(T[i])
  56. for(P=n,j=i;!v[j];v[j]=1,j=F[j],P--)
  57. P-=L[j]-L[F[j]]-1,C[F[j]][s[P]-'a']=j;
  58. //build SA&Height
  59. for(dfs(1),i=1;i<=n;i++)R[S[i]]=i;
  60. for(i=1;i<=n;h[R[i++]]=k)
  61. for(k?k--:0,j=S[R[i]-1];s[i+k]==s[j+k];k++);
  62. //find (l,r] offline with dsu
  63. for(int i=1;i<=n;i++)ll[i]=f[i]=i,ff[i]=i+1;
  64. sort(ff+1,ff+n,cmph);
  65. for(int i=1,j=1,u,p,q;j<=as;j++)
  66. {
  67. for(;h[ff[i]]>E[j].d&&i<n;i++)
  68. p=fd(ff[i]-1),q=fd(ff[i]),f[p]=q,ll[q]=ll[p];
  69. //insert queries for BIT
  70. u=fd(R[E[j].c]);
  71. Q[tot++]=(poi){u,E[j].a,E[j].b-E[j].d,E[j].i,1};
  72. Q[tot++]=(poi){ll[u]-1,E[j].a,E[j].b-E[j].d,E[j].i,-1};
  73. }
  74. sort(Q,Q+tot,cmpQ);
  75. //find the answer offline with BIT
  76. for(int i=0,j=1;i<tot;i++)
  77. {
  78. for(;j<=Q[i].a&&j<=n;j++)add(S[j]);
  79. ans[Q[i].i]+=Q[i]._*(ask(Q[i].c)-ask(Q[i].b));
  80. }
  81. }
  82. int main()
  83. {
  84. //Read-in&construct the string
  85. int _=read();
  86. for(int i=1;i<=_;i++)
  87. {
  88. int opt=read();
  89. if(opt==5)as++,E[as]=(Ask){sf,sb,tf,tb,as};
  90. else
  91. {
  92. char G;
  93. while('a'>c||'z'<c)G;
  94. if(opt==1)Sf[sf++]=c;
  95. if(opt==2)Sb[sb++]=c;
  96. if(opt==3)Tf[tf++]=c;
  97. if(opt==4)Tb[tb++]=c;
  98. }
  99. }
  100. for(int i=1;i<=sf;i++)s[++n]+=Sf[sf-i];
  101. for(int i=0;i<sb;i++)s[++n]+=Sb[i];
  102. s[++n]='{';
  103. for(int i=1;i<=tf;i++)s[++n]+=Tf[tf-i];
  104. for(int i=0;i<tb;i++)s[++n]+=Tb[i];
  105. //Handle queries
  106. for(int i=1;i<=as;i++)
  107. E[i].a=sf-E[i].a,E[i].b=sf+E[i].b,E[i].c=1+tf-E[i].c+sf+sb+1,E[i].d=tf+E[i].d+sf+sb+1-E[i].c;
  108. sort(E+1,E+1+as,cmpA);
  109. work();
  110. for(int i=1;i<=as;i++)printf("%d\n",ans[i]);
  111. return 0;
  112. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注