后缀自动机之统计子串相同个数

小咪咪 2021-11-22 02:42 370阅读 0赞

这个东西太难理解了，自己投入了大概，，，20个小时，三天。

但是学会之后就觉得是个渣渣，建议大家去洛谷看例题和博客。

推荐一个博客  [https://www.luogu.org/blog/Kesdiael3/hou-zhui-zi-dong-ji-yang-xie][https_www.luogu.org_blog_Kesdiael3_hou-zhui-zi-dong-ji-yang-xie]

我只读了6遍，就读懂了。

先做一个笔记：

简述自动机构造过程，

一开始有个空状态，然后添加字符，

然后从长到短遍历这个旧状态的所有后缀，并为那些后缀添加这个字符

如果某个后缀后面存在这个字符了或者已经更新完所有的了，那么就不用更新更短的后缀的，更新退出。

如果是更新完所有的，那么使这个新状态的后缀连接指向空状态

如果不是更新完所有的，那么又是两种情况：

1.  已经含有这个字符后缀的长度是原来字符的长度+1，也就是它们是连续的，中间不存在其他后缀。那么使新的状态的后缀连接指向那个遍历到的后缀状态
2.  已经含有这个字符后缀的长度不是原来字符的长度+1，也就是这两个字符之间仍旧有其他字符，根据后缀从长到短遍历的情况，这不符合相邻后缀相差1的性质。说明了虽然这个后缀已经存在了，但是它存在的那个状态含有更长的子串。那个后缀不能作为新的节点的后缀。然而新的状态仍旧需要一个后缀，来完成自己将来“从长到短遍历完所有后缀的动作”。解决办法是建立一个新的状态，这个状态赋值那个不符合条件后缀状态，但是长度改变为合法。然后遍历所有指向这个不符合条件状态的后缀的所有状态，让他们指向这个克隆状态。不符合条件状态的那些比较长的后缀状态仍旧指向自己。  最后一步：使不符合条件状态的后缀连接指向这个克隆状态，新状态的后缀连接指向这个状态、

洛谷例题：求每个子串的次数。

思路，构造出后缀自动机后，求出后缀parent tree，然后统计个数，然后每个状态有相应的长度，乘一下就好了

洛谷P3804

#include<bits/stdc++.h>
    using namespace std;
    const int M=5e6+50;
    struct Node{int len,fa,ch[26];}dian[M];
    char s[M];
    int n,tot=1,las=1,siz[M],head[M],cnt=1;
    struct edge{int next,to;}e[M];
    void add(int c){
    	int p=las,np=las=++tot;
    	siz[tot]=1;	
    	dian[np].len=dian[p].len+1;//更新长度
    	for(;p&&!dian[p].ch[c];p=dian[p].fa)dian[p].ch[c]=np;
    	if(!p)dian[np].fa=1;
    	else{
    		int q=dian[p].ch[c];
    		if(dian[q].len==dian[p].len+1)dian[np].fa=q;//找到上一个后缀 
    		else{
    			int nq=++tot;
    			dian[nq]=dian[q];
    			dian[nq].len=dian[p].len+1;
    			dian[q].fa=dian[np].fa=nq;
    			for(;p&&dian[p].ch[c]==q;p=dian[p].fa)dian[p].ch[c]=nq;
    		}
    	}
    }
    void addedge(int x,int to){
    	e[cnt].to=to;
    	e[cnt].next=head[x];
    	head[x]=cnt++;
    }
    int ans=0;
    void  dfs(int x){
    	for(int i=head[x];i!=-1;i=e[i].next){
    		dfs(e[i].to);
    		siz[x]+=siz[e[i].to];//从根节点遍历，首先碰到的是一个比较短的后缀。然后统计包含这个后缀，并且比它长的哪些后缀个数
    	}
    	if(siz[x]!=1)ans=max(ans,siz[x]*dian[x].len);
    }
    int main(){ 
    	scanf("%s",s+1);
    	n=strlen(s+1);
    	memset(head,-1,sizeof(head));
    	for(int i=1;i<=n;i++)add(s[i]-'a');//线性构造后缀自动机
    	for(int i=2;i<=tot;i++)addedge(dian[i].fa,i);
    	dfs(1);//然后dfs计算每个串的次数
    	printf("%d",ans);
    	return 0;
    }

[https_www.luogu.org_blog_Kesdiael3_hou-zhui-zi-dong-ji-yang-xie]: https://www.luogu.org/blog/Kesdiael3/hou-zhui-zi-dong-ji-yang-xie