[模板]后缀自动机

传送门

Description

给定一个只包含小写字母的字符串(S),

请你求出 (S) 的所有出现次数不为 (1) 的子串的出现次数乘上该子串长度的最大值。

Solution

保持好习惯吧，模板题还是放一下

SAM的板子，想必是到处都有，反正都比我写的好看。。。

当初想学SAM的时候，就被某俄文翻译的(20000)字论文吓跑了。。。

核心？

作为一种可以表示所有后缀的状态的自动机，它得满足状态数尽可能的小

SAM的做法：

每个状态表示所有(Right)集合相同的子串，这里(Right)集合的定义可是一个子串在原串中所有出现位置的右端点的集合。

对于每个状态，我们定义一个(step)，表示该状态所能表示的所有子串中长度最大值

(fa)指针，满足当前串的(Right)集合是(fa)指向的状态的真子集，且是最大的那一个，可以发现，(fa)指针所指向的状态一定是当前状态子串的一个后缀。

在线加点，每次加点后最多只会增加两个新的状态

Code

#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
class Suf_Automation
{
	#define MX 2000005
	private:
		int c[MX][26],fa[MX],step[MX],v[MX],rk[MX],val[MX];
		int last,cnt,n;
		ll ans=0;
	public:
		inline void init(int len)
    	{
        	cnt=last=1;n=len;
        	for(int i=1;i<=n<<1;++i)
            memset(c[i],0,sizeof c[i]),step[i]=fa[i]=v[i]=val[i]=0;
    	}
		void Insert(int x)
		{
    		int p=last,np=++cnt;step[np]=step[p]+1;val[np]=1;
        	for(;p&&!c[p][x];p=fa[p]) c[p][x]=np;
        	if(!p) fa[np]=1;
        	else 
        	{
        	    int q=c[p][x];
        	    if(step[q]==step[p]+1) fa[np]=q;
        	    else 
        	    {
        	        int nq=++cnt;step[nq]=step[p]+1;
        	        memcpy(c[nq],c[q],sizeof c[q]);
        	        fa[nq]=fa[q];fa[np]=fa[q]=nq;
        	        for(;c[p][x]==q;p=fa[p]) c[p][x]=nq;
        	    }    
        	}
        	last=np;
		}
		inline void Query()
		{
			register int i;
			for(i=1;i<=cnt;++i) ++v[step[i]];
        	for(i=1;i<=n;++i) v[i]+=v[i-1];
        	for(i=1;i<=cnt;++i) rk[v[step[i]]--]=i;
        	for(i=cnt;i;--i)
			{
				val[fa[rk[i]]]+=val[rk[i]];
				if(val[rk[i]]>1) ans=max(ans,1ll*val[rk[i]]*step[rk[i]]);
			}
			val[1]=0;
    		printf("%lld
",ans);
		}
	#undef MX
}pac;
#define MN 1000005
char s[MN];
int main()
{
	scanf("%s",s+1);
	register int i,n=strlen(s+1);
	pac.init(n);
	for(i=1;i<=n;++i) pac.Insert(s[i]-'a');
	pac.Query();
	return 0;
}

SAM的作用？

很好的维护子串信息的工具嘛。

下面附上一个简单的，查询某个串的出现次数?

int Calc(char*s,int l,int r)
{
	int x=1;
    for(int i=l;i<=r;++i)
    	if(!c[x][s[i]-'a']) return 0;
        else x=c[x][s[i]-'a'];    
    return val[x];
}

可以发现，顺着SAM查询子串，到达的状态是所有与查询的子串出现情况相类似（出现次数肯定是相同的）的子串集合，当然，待查子串也在这个集合里辣。

Blog来自PaperCloud，未经允许，请勿转载，TKS！