[SDOI2016]生成魔咒（后缀自动机）

看一眼题。本质不同的字串数。

嘴角微微上扬。

每一次加一个数输出一个答案。

笑容渐渐消失。

等等，\(SAM\)好像也可以求本质不同的字串。

设当前字符串用\(x\)表示，每次插入完成后\(ans\)加上\(len[x]-len[fa]\)就行了。

嘴角微微上扬。

等等，炸空间了。

笑容渐渐消失。

用\(map\)不就得了。

嘴角再次上扬。

写完过了。

笑出了声。

翻题解，时看到了\(SA\)。

笑容渐渐僵硬。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<map>

using namespace std;

#define int long long

const int N=101000;

int n,ans;

struct SAM{

	int tot,u,len[N*2],fa[N*2];

	map<int,int>trans[N*2];

	void init(){tot=u=1;}

	void ins(int c){

		int x=++tot;len[x]=len[u]+1;

		for(;u&&trans[u][c]==0;u=fa[u])trans[u][c]=x;

		if(u==0)fa[x]=1,ans+=len[x];

		else{

			int v=trans[u][c];

			if(len[u]+1==len[v])fa[x]=v,ans+=len[x]-len[v];

			else{

				int w=++tot;len[w]=len[u]+1;

				trans[w]=trans[v];

				fa[w]=fa[v];

				fa[x]=fa[v]=w;

				ans+=len[x]-len[w];

				for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=w;

			}

		}

		u=x;

	}

}sam;

int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return sum*f;

}

signed main(){

	n=read();

	sam.init();

	for(int i=1;i<=n;i++){

		sam.ins(read());

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

[SDOI2016]生成魔咒（后缀自动机）

最新文章

热门文章