锐客网

  1. 首页 > it技术 > >

字符串家族|字符串家族 学习笔记

本来想着一天速通字符串，看来我还是想多了。
可能需要的前置

  • 字符串哈希
  • KMP
  • trie 树
  • manacher 算法
可能涵盖的内容 目前已有的：
  • 后缀数组 SA
  • AC 自动机
未来可能会有的：
  • 扩展 KMP
  • 后缀自动机
  • 回文自动机
  • 子序列自动机
本文可能会有很多错误，还请发现的大佬们指出，本蒟蒻感到非常荣幸。
参考资料
  • 后缀数组
xMinh大佬 的 讲解
Rainy7大佬 的 学习笔记
曲神学长 的 算法总结
Ckj 同机房大佬 的 学习笔记
  • AC 自动机
Hastieyua 大佬 的 详细讲解
对此，本蒟蒻不胜感激
如有侵权问题，请联系我，我会马上标明出处或修改。
后缀数组 后缀排序
模板题：P3809 【模板】后缀排序
后缀数组可以用来实现一个字符串的每个后缀按照字典序排序的操作，根据这个操作，可以引申出很多用法。
后缀数组 SA 的实现是基于基数排序的思想，在普通基数排序的基础上加了倍增。
算法流程大致如下：
这里假设待排序字符串是 abacabc。
  • 首先用一个字母进行排序，结果更新到一个 rk 数组（表示该后缀排名），上述字符串应为 1 2 1 3 1 2 3。
  • 然后相邻两个字符串拼接起来，对于每个后缀，得到它长度为 \(2\) 的前缀的两位标号。对于最后一个长度为 \(1\) 的后缀，因为没有第二位字符串，所以它第二位字典序最小，通过补零解决。此时上述字符串的标号为 12 23 13 31 12 23 30。
  • 然后对这些原来相同的后缀们重新排序，标号变成 1 3 2 5 1 3 4。
  • 然后我们重复第二步过程，让每个后缀和它隔一个的那个后缀拼接起来，得到它长度为 \(4\) 的前缀的两位标号。同理，不够的补零。此时上述字符串标号为 12 35 21 53 14 30 40，注意要隔一个，因为现在每一位代表的是两个字符的字符串的排序。
  • 然后重新排序，得到 1 5 3 7 2 4 6。
  • 我们发现现在标号已经没有重复了的，得到的数字即是对应后缀在所有后缀中的排名。
我们发现这样子每次每个后缀的长度会 \(\times2\)，所以最多只会进行 \(O(\log n)\) 次拼接-标号过程，每次都是 \(O(n)\) 时间，总时间复杂度 \(O(n\log n)\)。
其实后缀数组还有另外一个算法 DC3，能做到时间复杂度 \(O(n)\)，可是由于本蒟蒻不会 代码复杂度过高，而且空间复杂度不优，我们还是常用 SA。
为了方便后面的使用，这里封装成了结构体。
#include using namespace std; const int N=1e6+10; int n; char s[N]; struct SA{ int m=131,x[N],y[N],c[N],sa[N],nx[N],hei[N]; void get_sa(){ for(int i=1; i<=n; i++)c[x[i]=s[i]]++; //处理第一个字符的排序 int l=0; for(int i=1; i<=m; i++)c[i]+=c[i-1]; for(int i=n; i>=1; i--)sa[c[s[i]]--]=i; for(int k=1; k<=n; k<<=1){ int num=0; for(int i=n-k+1; i<=n; i++)y[++num]=i; //后面的字符串已经排好序了，不需要加入排序 for(int i=1; i<=n; i++)if(sa[i]>k)y[++num]=sa[i]-k; for(int i=1; i<=m; i++)c[i]=0; //桶排 for(int i=1; i<=n; i++)c[x[i]]++; for(int i=2; i<=m; i++)c[i]+=c[i-1]; for(int i=n; i>=1; i--)sa[c[x[y[i]]]--]=y[i],y[i]=0; //倒序附排名，保证排序稳定 swap(x,y); num=1,x[sa[1]]=1; for(int i=2; i<=n; i++){//处理下一次排序的关键字 if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=num; //若两个都相等，那么当前两个后缀是相同的 else x[sa[i]]=++num; } if(num==n)break; //如果已经排完了，就不管了 m=num; } } }sa; signed main(){ scanf("%s",s+1),n=strlen(s+1); sa.get_sa(); for(int i=1; i<=n; i++)printf("%d ",sa.sa[i]); puts(""); }

注意，在上述代码中，sa 数组存的是排名为 \(i\) 的后缀的第一个字符在原串中的位置，不要搞混了。如果要求 第 \(i\) 个后缀的排名，也就是上述解释中的标号，需要再进行转化。因为 \(sa\) 和 \(rk\) 是互逆的，也就是 \(sa_{rk_i}=i\)，所以这个过程比较简单，便不再赘述。
评测结果
当然，这只是万里长征路中的微不足道的一步，但同时也是意义非凡的一步。
后缀数组的运用：height 数组与 LCP
先摆出一些定义：
\(rk_i\) 表示第 \(i\) 个后缀的排名。
\(lcp(s,t)\) 表示两个字符串 \(s\) 和 \(t\) 它们的最长公共前缀，在本文中，表示编号分别为 \(s,t\) 的两个后缀的最长公共前缀。
\(hei_i=lcp(sa_i,sa_{i-1})\)，也就是排名为 \(i\) 和 \(i-1\) 的两个后缀的最长公共前缀。
\(h_i=hei_{rk_i}\)，也就是当前后缀与比他排名前一位的后缀最长公共前缀。
接下来，是一些性质。
性质 1：\(lcp(i,j)=lcp(j,i)\)。
并不需要什么证明。
性质 2：\(lcp(i,i)=n-sa_i+1\)。
可以发现，两个完全一样的字符串它们的最长公共前缀就是它本身，长度为 \(n-sa_i+1\)。
性质 3 LCP Lemma：\(lcp(i,j)=\min(lcp(i,k),lcp(k,j))(1\le i\le k\le j \le n)\)。
这里开始有点烧脑了。
设 \(p=\min(lcp(i,k),lcp(k,j))\)，则有 \(lcp(i,k)\ge p,lcp(k,j)\ge p\)。
设 \(sa_i,sa_j,sa_k\) 所代表的后缀分别是 \(u,v,w\)。
得到 \(u,w\) 前 \(p\) 个字符相等，\(w,v\) 前 \(p\) 个字符也相等，
所以得到 \(u,v\) 前 \(p\) 个字符也相等，
设 \(lcp(i,j)=q\)，则有 \(q\ge p\)。
接下来，我们采用反证法证明 \(q=p\)。
假设 \(q>p\)，即 \(q\ge p+1\)。
因此 \(u_{p+1}=v_{p+1}\)。
因为 \(p=\min(lcp(i,k),lcp(k,j))\)，所以有 \(u_{p+1}\not=w_{p+1}\) 或 \(v_{p+1}\not=w_{p+1}\)。
所以得到 \(u_{p+1}\not=v_{p+1}\)，与前面矛盾。
因此得到 \(q\le p\)，综合得 \(q=p\)，即 \(lcp(i,j)=\min(lcp(i,k),lcp(k,j))(1\le i\le k \le j \le n)\)。
性质 4 LCP Theorem：\(lcp(i,j)=\min(lcp(k,k-1))(1
我们可以用刚得到的性质三来证。
\(lcp(i,j)=\min(lcp(i,i+1),lcp(i+1,j))\\=\min(lcp(i,i+1),\min(lcp(i+1,i+2),lcp(i+2,j))\\=\dots=min(lcp(k,k-1))(i\le k\le j)\)
性质 5：\(h_i\le h_{i-1}-1\)。
转载至简书-信息学小屋：
字符串家族|字符串家族 学习笔记
文章图片

回归正题，设 \(hei_1=0\)，考虑如何求 \(hei\)。
因为 \(lcp(i,j)=min(lcp(k,k-1))(1 所以 \(lcp(i,j)=min(hei_k)(i 前面有提过 \(sa_{rk_i}=i\)，所以 \(hei_{i}=h_{sa_i}\)。
我们先把 \(h\) 求出来，然后就能利用性质 4，用 rmq 之类的东西求一下，能做到 \(O(1)\) 查询。
int n,lg[N]; char s[N]; struct SA{ int m=131,x[N],y[N],c[N],sa[N],rk[N],nx[N],hei[N],h[N]; int mn[N][20]; void get_sa(){ for(int i=1; i<=n; i++)c[x[i]=s[i]]++; //处理第一个字符的排序 int l=0; for(int i=1; i<=m; i++)c[i]+=c[i-1]; for(int i=n; i>=1; i--)sa[c[s[i]]--]=i; for(int k=1; k<=n; k<<=1){ int num=0; for(int i=n-k+1; i<=n; i++)y[++num]=i; //后面的字符串已经排好序了，不需要加入排序 for(int i=1; i<=n; i++)if(sa[i]>k)y[++num]=sa[i]-k; for(int i=1; i<=m; i++)c[i]=0; //桶排 for(int i=1; i<=n; i++)c[x[i]]++; for(int i=2; i<=m; i++)c[i]+=c[i-1]; for(int i=n; i>=1; i--)sa[c[x[y[i]]]--]=y[i],y[i]=0; //倒序附排名，保证排序稳定 swap(x,y); num=1,x[sa[1]]=1; for(int i=2; i<=n; i++){//处理下一次排序的关键字 if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=num; //若两个都相等，那么当前两个后缀是相同的 else x[sa[i]]=++num; } if(num==n)break; //如果已经排完了，就不管了 m=num; } for(int i=1; i<=n; i++)rk[sa[i]]=i; } void get_h(){ for(int i=1,k=0; i<=n; i++){ int j=sa[rk[i]-1]; k-=(k!=0); while(s[i+k]==s[j+k])++k; h[i]=hei[rk[i]]=k; } } void rmq(){ for(int i=2; i<=n; i++)lg[i]=lg[i>>1]+1; for(int i=1; i<=n; i++){ mn[i][0]=hei[i]; for(int j=1; i>=(1<r)swap(l,r); ++l; int d=lg[r-l+1]; return min(mn[r][d],mn[l+(1<

后缀数组的简单运用 例 1：P2408 不同子串个数
题目大意：统计一个字符串中本质不同的子串个数。
ps：本题可以用后缀自动机做，但同时也是后缀数组好题。
正难则反，我们考虑计算所有子串个数减去相同子串个数。
我们求出 \(hei\) 之后，剪掉相同前缀数量即可。
由于篇幅问题，本文中例题只放主要代码。
signed main(){ scanf("%lld%s",&n,s+1); sa.get_sa(),sa.get_h(); int ans=n*(n+1)/2; for(int i=1; i<=n; i++)ans-=sa.hei[i]; printf("%lld\n",ans); }

评测记录
例 2：P3763 [TJOI2017]DNA
题目大意：给出两个串 \(S_0\) 和 \(S\)，求 \(S_0\) 中有多少个长度和 \(S\) 相同的子串，使得这个子串能通过修改 \(\le 3\) 个字符与 \(S\) 相同。多组询问。
ps：本题似乎有多项式做法，有兴趣的可以了解一下。
我们可以把 \(S\) 插入到 \(S_0\) 后面，中间用一个精心挑选的分隔符，然后就可以得到 \(S_0\) 的每个后缀和 \(S\) 的 lcp 了。
然后枚举每一个开头，和 \(S\) 的 lcp 暴力往后跳，跳到一个不匹配的位置就跳过，只要跳完后失配点不超过三个 就能统计。处理以每个字符开头的子串时间复杂度 \(O(1)\)。
因为是多测，注意封装函数时是否清空函数，宁愿多清也不漏清。
int _; scanf("%d",&_); for(; _--; ){ scanf("%s%s",s+1,t+1); k=n=strlen(s+1),m=strlen(t+1); s[++n]='#'; for(int i=1; i<=m; i++)s[++n]=t[i]; sa.get_sa(),sa.get_h(),sa.rmq(); int ans=0; for(int i=1; i<=k-m+1; i++){ int __=0; for(int j=1; __<=3&&j<=m; ){ //printf("%d %d\n",i,j); if(s[i+j-1]^s[k+j+1])++j,++__; else j+=sa.lcp(sa.rk[i+j-1],sa.rk[k+j+1]); } if(__<=3)++ans; } printf("%d\n",ans); }

下面给出几道题作为练习。
评测记录
P4248 [AHOI2013]差异
P4051 [JSOI2007]字符加密
P1117 [NOI2016] 优秀的拆分
CF1043G Speckled Band
接下来，后缀数组的事情可能就要告一段落了。
AC 自动机 AC 自动机作为自动机家族里面几乎是最容易入手的一个，这里介绍一下。
这一部分需要读者能够深刻理解 trie，了解 kmp。
从 kmp 到 AC 自动机
我们回忆一下 kmp 是处理什么问题的：单模式串匹配问题。
那如果很多个模式串和一个文本串匹配呢？
这时候，AC 自动机重磅出击！
首先有个很 naive 的想法，把模式串们放进一个 trie 树上，然后枚举每一个文本串的后缀，放上去匹配一下。
举个例子，假设我们有模式串 abc，abb，bcc，文本串 abccabbcc。
那么我们建出来的 trie 树大概就是这样。
字符串家族|字符串家族 学习笔记
文章图片

这个时候如我们先匹配 a，然后走到 abc，发现匹配不了了，倒回起点，从 b 开始匹配，匹配到 bcc。
思考：如果这样子下去，我们会发现这个思路绝对会 T。
考虑如何优化这个过程。
我们发现，我们从 abc 走到下一个 c 时，没有办法匹配，我们把这个情况叫做失配。但是，如果把开头的 a 扔掉，我们发现我们能够走到 bcc。也就是说，每次失配时，我们可以把一些前缀扔掉，走到另外一个能让它不失配的点，这样次就不需要每次失配都倒回起点重头再来。
如果我们对每个点，向它丢掉最短非空前缀之后的点连一条边，（保证状态尽量长）那么，每次失配了就跳到上一个点上就好了。
练完之后的图大概长这样：
字符串家族|字符串家族 学习笔记
文章图片

我们把这样练得边叫做 fail 指针。
我们考虑这样匹配：从字典树的根节点开始依次添加匹配串的字符。遇到失配时，顺着 fail 指针找到能匹配新字符的第一个状态。若当前状态 fail 链上的某个祖先是终止状态，则成功匹配模式串 。
考虑如何快速找到失配点，如果有这个儿子，可以把 fail 指针指向父亲的对应 fail 指针，否则把儿子设为父亲的对应 fail 指针，方便之后的更新。这里可以用类似广搜的方法更新，详见代码。
如果我们查询的时候暴力向上跳失配点，直到根节点，统计答案，这样的话时间复杂度最多能被卡到 \(O(模式串长\times 文本串长)\)，能过 P3796 【模板】AC 自动机（加强版），但是过不了 P5357 【模板】AC 自动机（二次加强版）。
这些操作是依据 trie 树的，因此 AC 自动机也被称作 trie 图。
void push(char *s,int k){ int p=0,len=strlen(s+1); for(int i=1; i<=len; i++){ int c=s[i]-'a'; if(!tr[p][c])tr[p][c]=++tot; p=tr[p][c]; } vis[num[k]=p]=1; } void get_fail(){ queue q; for(int i=0; i<26; i++){ if(tr[0][i])q.push(tr[0][i]); } while(!q.empty()){ int p=q.front(); q.pop(); for(int i=0; i<26; i++){//最难理解的部分 if(tr[p][i])fail[tr[p][i]]=tr[fail[p]][i],q.push(tr[p][i]); else tr[p][i]=tr[fail[p]][i]; } } } void find(char *s){ int len=strlen(s+1); int p=0; for(int i=1; i<=len; i++){ int c=s[i]-'a'; p=tr[p][c]; for(int k=p; k; k=fail[k])ans[k]++; } }

加强版评测记录
我们继续考虑优化这个过程。
我们发现在原来暴力跳的过程中，我们每经过一次 abc，都要统计一次 bc，如果有 c 的话也要跟的统计，非常麻烦，所以我们考虑能不能一次性统计完。比如我们到达一个点打一个标记，打完标记后统一上传，这样就能够优化这个过程了。
那么，我们如何确定上传顺序呢？
拓扑排序！
我们在统计答案的时候打一个标记，然后用类似拓扑排序的方法，从深度大的点更新到深度小的点。
void find(char *s){ int len=strlen(s+1); int p=0; for(int i=1; i<=len; i++){ int c=s[i]-'a'; ans[p=tr[p][c]]++; } queue q; for(int i=1; i<=tot; i++)if(!d[i])q.push(i); while(!q.empty()){ int u=q.front(); q.pop(); int v=fail[u]; d[v]--,ans[v]+=ans[u]; if(!d[v])q.push(v); } }

评测记录
至此，你已能通过谷上三道模板题了。
AC自动机的简单运用
例 1：P3966 [TJOI2013]单词
模板题，不讲（
例 2：P3121 [USACO15FEB]Censoring G
题目大意：给你一个文本串和一堆模式串，在文本串中找到出现位置最靠前的模式串并删掉，重复这个过程，求最后的文本串。
注意有删除操作，所以我们可以把扫到的节点放到一个栈里面，每次匹配到了就倒退回去就好了。
为了方便输出，我用了 deque 实现。
因为不需要在自动机上统计什么答案，所以也不需要拓扑优化。
inline void find(string s){ deque q; register int p=0; q.push_back({' ',0}); for(register int i=0; i

评测记录
例 3：P2292 [HNOI2004] L 语言
题目大意：给出若干个模式串，每次询问一个文本串最长的能被模式串们完全匹配的前缀长度。
属于在 AC 自动机上跑简单 dp。
我们考虑到这建 AC 自动机。
设 \(f_i\) 表示前缀 \(i\) 是否完全匹配，枚举每一个前缀，到这从这一位往前找，每次加入一个点，如果适配了就直接弹（因为必须要完全匹配）。
考虑模式串比较小，所以这样做是可行的。
当然正解是在 AC 自动机上状压，具体可见 扶苏大佬 的 题解。
for(int i=1; i<=len; i++){ f[i]=false; pos=0; for(int j=i; j>=1; j--){ if(!trie[pos][t[j]-'a'])break; pos=trie[pos][t[j]-'a']; if(vis[pos]){ f[i]|=f[j-1]; if(f[i])break; } } }

评测记录
接下来是几道练习，可能有点困难。
P5231 [JSOI2012]玄武密码 ps：也能用后缀数组做。
P2414 [NOI2011] 阿狸的打字机
P3763 [TJOI2017]DNA ps：刚刚在后缀数组有，但是也可以在 AC 自动机上 dp。
P3735 [HAOI2017]字符串
Loj 668 yww 与树上的回文串 ps：点分治与 AC 自动机结合。
【字符串家族|字符串家族 学习笔记】51nod1600 Simple KMP ps：对 fail 链的深刻理解，与 LCT 结合。

    推荐阅读


    上一篇：自己动手写Vector【Cherno|自己动手写Vector【Cherno C++教程】

    下一篇：安卓开源框架学习|OKHttp原理讲解之基本概念