SDOI 2016 生成魔咒题解-白红宇

SDOI 2016 生成魔咒题解

阅读量：2307 次

发布时间：2019-05-09

本文共 1043 字，大约阅读时间需要 3 分钟。

题目大意： 给出一个字符串，询问它的每一个前缀内包含多少个不同的子串。

题解

将字符一个一个加入到SAM里，每个新的字符的的贡献为 $l e n (x) - l e n (l i n k (x))$ ，因为从 $l e n (l i n k (x))$ 这个长度开始，下面的长度的后缀都已经出现过了，只有上面的后缀是没出现过的，即新的不同的子串。

代码如下：

#include 
   
    #include 
    
     #include 
     #include 
      
       using namespace std;#define maxn 200010int n;long long ans=0;struct state{
   	int len,link;	map
       
         next;}st[maxn];int id=0,last=0,now,p,q;void extend(int x){
   	now=++id;	st[now].len=st[last].len+1;	for(p=last;p!=-1&&!st[p].next.count(x);p=st[p].link)st[p].next[x]=now;	if(p!=-1)	{
   		q=st[p].next[x];		if(st[p].len+1==st[q].len)st[now].link=q;		else		{
   			int clone=++id;			st[clone]=st[q];st[clone].len=st[p].len+1;			for(;p!=-1&&st[p].next[x]==q;p=st[p].link)st[p].next[x]=clone;			st[q].link=st[now].link=clone;		}	}	last=now;}int main(){
   	scanf("%d",&n);	st[0].link=-1;	for(int i=1,x;i<=n;i++)	{
   		scanf("%d",&x);		extend(x);		ans+=st[now].len-st[st[now].link].len;		printf("%lld\n",ans);	}}

转载地址：http://ajnib.baihongyu.com/

你可能感兴趣的文章

php源码之路第三章第六节（变量的生命周期之变量的赋值和销毁）