Codeforces 316G3 Good Substrings 字符串 SAM

时间：2023-03-08 15:59:16

原文链接http://www.cnblogs.com/zhouzhendong/p/9010851.html

题目传送门 - Codeforces 316G3

题意

　　给定一个母串$s$，问母串$s$有多少本质不同的子串$t$是“好”的。

　　一个字符串$t$是好的，仅当$t$满足了所有的$n$个条件。

　　第$i$个条件用一个三元组$(p_i,L_i,R_i)$来描述。

　　其中$p_i$为一个字符串，$L_i,R_i$为整数，且$L_i\leq R_i$。

　　仅当字符串$t$在$p_i$中出现次数在$L_i$到$R_i$之间时，它是"好"的。

　　$|s|,|p_i|\leq 5\times 10^4,n\leq 10$

题解

　　考虑把输入的$n+1$个字符串用特殊字符隔开，并练成一个串。

　　为了方便，我们将母串$s$放在第一个，$n$条规则中的字符串依次连续。

　　我们定义数组$tot[i][j]$表示后缀自动机状态$i$的$Right$集合中有多少个位置处于第$j$个串。其中母串为第$0$个串，$p_i$为第$i$个串。

　　这个可以通过基数排序+$dp$来搞定。

　　然后我们分状态统计。

　　对于状态$i$，如果$tot[i][0]=0$，那么说明这个状态所表示的一些串不存在于母串中，所以可以跳过。

　　否则$tot[i][0]>0$，这个状态所表示的一些串存在于母串中。由于母串中没有特殊的字符，所以这个状态所表示的一些串也没有特殊字符，所以，对于已经得到的计数$tot[i][1\cdot n]$中也没有统计到包含特殊字符的子串。

　　如果当前状态被计入，那么需要满足所有的$n$个条件，即$\forall 1\leq j\leq n,\ \ L_j\leq tot[i][j]\leq R_j$。当前状态包含的本质不同的串的个数显然为$Max(i)-Min(i)+1=Max(i)-Max(fa(i))$。加到答案里就可以了。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=550005;

int n,m,L[15],R[15];

int size=1,root=1,last=1;

int tax[N<<1],id[N<<1];

LL tot[N<<1][12];

char s[N];

struct SAM{

	int Next[27],fa,Max;

}t[N<<1];

void extend(int c,int id){

	int p=last,np=++size,q,nq;

	tot[np][id]++;

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

	for (;!t[p].Next[c];p=t[p].fa)

		t[p].Next[c]=np;

	q=t[p].Next[c];

	if (t[q].Max==t[p].Max+1)

		t[np].fa=q;

	else {

		nq=++size;

		t[nq]=t[q],t[nq].Max=t[p].Max+1;

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

		for (;t[p].Next[c]==q;p=t[p].fa)

			t[p].Next[c]=nq;

	}

	last=np;

}

int main(){

	t[0].Max=-1;

	for (int i=0;i<27;i++)

		t[0].Next[i]=1;

	scanf("%s",s);

	m=strlen(s);

	for (int i=0;i<m;i++)

		extend(s[i]-'a',0);

	scanf("%d",&n);

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

		extend(26,n+1);

		scanf("%s%d%d",s,&L[i],&R[i]);

		m=strlen(s);

		for (int j=0;j<m;j++)

			extend(s[j]-'a',i);

	}

	for (int i=1;i<=size;i++)

		tax[t[i].Max]++;

	for (int i=1;i<=size;i++)

		tax[i]+=tax[i-1];

	for (int i=1;i<=size;i++)

		id[tax[t[i].Max]--]=i;

	LL ans=0;

	for (int i=size;i>=2;i--){

		int x=id[i];

		for (int j=0;j<=n;j++)

			tot[t[x].fa][j]+=tot[x][j];

		if (tot[x][0]==0)

			continue;

		bool flag=1;

		for (int j=1;flag&&j<=n;j++)

			flag&=L[j]<=tot[x][j]&&tot[x][j]<=R[j];

		if (flag)

			ans+=t[x].Max-t[t[x].fa].Max;

	}

	printf("%I64d",ans);

	return 0;

}

　　

相关文章