字符串家族 学习笔记

本来想着一天速通字符串，看来我还是想多了。

可能需要的前置

• 字符串哈希

• KMP

• trie 树

• manacher 算法

可能涵盖的内容

目前已有的：

• 后缀数组 SA

• AC 自动机

未来可能会有的：

• 扩展 KMP

• 后缀自动机

• 回文自动机

• 子序列自动机

本文可能会有很多错误，还请发现的大佬们指出，本蒟蒻感到非常荣幸。

参考资料

• 后缀数组

xMinh大佬 的 讲解

Rainy7大佬 的 学习笔记

曲神学长 的 算法总结

Ckj 同机房大佬 的 学习笔记

• AC 自动机

Hastieyua 大佬 的 详细讲解

对此，本蒟蒻不胜感激

如有侵权问题，请联系我，我会马上标明出处或修改。

后缀数组

后缀排序

模板题：P3809 【模板】后缀排序

后缀数组可以用来实现 代码复杂度过高，而且空间复杂度不优，我们还是常用 SA。

为了方便后面的使用，这里封装成了结构体。

#include<bits/stdc++.h>
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 数组存的是，具体可见 扶苏大佬 的 题解。

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 结合。

---