关于后缀自动机

本文不是教大家后缀自动机，只是扔两个板子

个人认为大多数基础题只要会板子就好了

建出 SAM ：

char s[N];
int ch[N][26],len[N],fa[N];
int las,cnt;
void insert(int c)
{
	int p=las,np=las=++cnt;
	len[np]=len[p]+1;
	for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
	if(!p) fa[np]=1;
	else
	{
		int q=ch[p][c];
		if(len[p]+1==len[q]) fa[np]=q;
		else
		{
			int nq=++cnt; len[nq]=len[p]+1;
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
			fa[nq]=fa[q];
			fa[q]=fa[np]=nq;
			for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
		}
	}
}

求出每个子串的出现次数

char s[N];
int ch[N][26],len[N],fa[N];
int las,cnt;
int tx[N],a[N],siz[N];
void insert(int c)
{
	int p=las,np=las=++cnt;
	len[np]=len[p]+1; siz[np]=1;
	for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
	// printf("%d %d
",c,p);
	if(!p) fa[np]=1;
	else
	{
		int q=ch[p][c];
		if(len[p]+1==len[q]) fa[np]=q;
		else
		{
			int nq=++cnt; len[nq]=len[p]+1;
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
			fa[nq]=fa[q];
			fa[q]=fa[np]=nq;
			for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
		}
	}
}
void solve()
{
	las=cnt=1;
	for(int i=1;i<=n;i++) insert(s[i]-'a');
	for(int i=1;i<=cnt;i++) tx[len[i]]++;
	for(int i=1;i<=cnt;i++) tx[i]+=tx[i-1];
	for(int i=1;i<=cnt;i++) a[tx[len[i]]--]=i;
	for(int i=cnt;i>=1;i--)
	{
		int u=a[i];
		siz[fa[u]]+=siz[u];
	}
	siz[1]=0;
}

动态询问不同子串个数

map<int,int> ch[N];
int len[N],fa[N],las,cnt;
ll ans;
void insert(int c)
{
	int p=las,np=las=++cnt;
	len[np]=len[p]+1;
	for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
	if(!p) fa[np]=1;
	else
	{
		int q=ch[p][c];
		if(len[p]+1==len[q]) fa[np]=q;
		else
		{
			int nq=++cnt;
			len[nq]=len[p]+1;
			ch[nq]=ch[q],fa[nq]=fa[q];
			ans+=len[nq]-len[fa[nq]];
			ans+=len[fa[q]];
			fa[q]=fa[np]=nq;
			ans-=len[fa[q]];
			for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
		}
	}
	ans+=len[np]-len[fa[np]];
}
void solve()
{
	int n=read();
	for(int i=1;i<=n;i++)
	{
		int a=read();
		insert(a);
		printf("%lld
",ans);
	}
}