【Hihocoder1413】Rikka with String（后缀自动机）

题面

Hihocoder

给定一个小写字母串，回答分别把每个位置上的字符替换为'#'后的本质不同的子串数。

题解

首先横跨'#'左右的串一定恰好只会出现一次，所以直接统计答案。

那么剩下的部分就是左右的本质不同的子串数。

我们把答案拆成三个部分，先是左侧本质不同子串的个数，再是右侧本质不同子串的个数。最后再减去既在左侧出现过，又在右侧出现过的串的个数。

左右两个直接用\(SAM\)算就好了。

在两侧同时出现过的，我们维护每一个节点最小的\(endpos\)和最大的\(endpos\)，显然'#'出现在两串之间的时候就会在左右同时被计算。

每个\(endpos\)表示的都是一段区间，这里就是做多个区间的区间加，所以二阶差分计算。

具体的东西看代码。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define ll long long

#define MAX 300300

int n;char ch[MAX];

struct Node

{

	int son[26];

	int ff,len;

}t[MAX<<1];

int last=1,tot=1;

ll ans[MAX],c1[MAX],c2[MAX],cnt=0;

int l[MAX<<1],r[MAX<<1];

void extend(int c,int id)

{

	int p=last,np=++tot;last=np;

	t[np].len=t[p].len+1;

	while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].ff;

	if(!p)t[np].ff=1;

	else

	{

		int q=t[p].son[c];

		if(t[q].len==t[p].len+1)t[np].ff=q;

		else

		{

			int nq=++tot;

			t[nq]=t[q];t[nq].len=t[p].len+1;

			t[q].ff=t[np].ff=nq;

			while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff;

		}

	}

	cnt+=t[np].len-t[t[np].ff].len;

	l[np]=r[np]=id;

}

int a[MAX<<1],p[MAX<<1];

int main()

{

	scanf("%d",&n);scanf("%s",ch+1);

	memset(l,63,sizeof(l));memset(r,0,sizeof(r));

	for(int i=1;i<=n;++i)extend(ch[i]-97,i),ans[i+1]+=cnt;

	for(int i=1;i<=n;++i)ans[i]+=1ll*i*(n-i+1);

	for(int i=1;i<=tot;++i)a[t[i].len]++;

	for(int i=1;i<=n;++i)a[i]+=a[i-1];

	for(int i=1;i<=tot;++i)p[a[t[i].len]--]=i;

	for(int i=tot;i>1;--i)

	{

		int u=p[i];

		l[t[u].ff]=min(l[t[u].ff],l[u]);

		r[t[u].ff]=max(r[t[u].ff],r[u]);

		int len=min(r[u]-l[u],t[u].len);

		if(len<=t[t[u].ff].len)continue;

		c1[l[u]+1]+=len-t[t[u].ff].len;

		c2[r[u]-t[t[u].ff].len+1]+=1;

		c2[r[u]-len+1]-=1;

	}

	for(int i=1;i<=n;++i)c2[i]+=c2[i-1];

	for(int i=1;i<=n;++i)c1[i]+=c1[i-1]+c2[i];

	for(int i=1;i<=n;++i)ans[i]-=c1[i];

	memset(t,0,sizeof(t));last=tot=1;cnt=0;

	for(int i=n;i;--i)extend(ch[i]-97,i),ans[i-1]+=cnt;

	for(int i=1;i<=n;++i)printf("%lld ",ans[i]);

	puts("");return 0;

}