首页 > 代码库 > CF271D_Good Substrings

CF271D_Good Substrings

2024-07-09 06:03:32   220人阅读

给一个原串，以及那些字符是坏的，现在问你可以从原串中取出多少个不同子串，使得其所含的坏字符的个数不超过一个定数。

这个题目网上有各种各样的解法。如hash，tire。

我说一下我的解法。

解法一：后缀自动机dp。f[][]保存到达某个状态，前面已经有的坏字符的个数的时候的字符串数量。这样按照拓扑序列一直递推下去就可以了。时间复杂度为O(N2)。

解法二：后缀自动机，预处理。对于字符串，每个位置保存它可以最前走到那个位置。然后，在自动机上增加信息，保存位置。然后直接按照距离判断就可以了。对于每个节点，直接缩小范围，更新答案。时间复杂度为O(N)。

 

召唤代码君：

 

#include <iostream>#include <cstdio>#include <cstring>#define maxn 3555using namespace std;char real[26],s[maxn];int next[maxn][26],pre[maxn],step[maxn];int N,last,n,L;int p,q,np,nq,ans=0;int f[maxn],tag[maxn],sum[maxn];void insert(int x,int ggg){	p=last,np=++N,step[np]=step[p]+1,last=np,tag[np]=ggg;	for (; p!=-1 && next[p][x]==0; p=pre[p]) next[p][x]=np;	if (p==-1) return;	q=next[p][x];	if (step[q]==step[p]+1) { pre[np]=q; return ; }	nq=++N,step[nq]=step[p]+1,pre[nq]=pre[q],tag[nq]=ggg;	for (int i=0; i<26; i++) next[nq][i]=next[q][i];	pre[np]=pre[q]=nq;	for (; p!=-1 && next[p][x]==q; p=pre[p]) next[p][x]=nq;}int main(){	scanf("%s",s+1);	scanf("%s",real);	scanf("%d",&n);	pre[0]=-1;  	L=strlen(s+1);	for (int i=1; s[i]; i++) insert(s[i]-‘a‘,i);	sum[0]=0;	for (int i=1; i<=L; i++)	{		sum[i]=sum[i-1];		if (real[s[i]-‘a‘]==‘0‘) sum[i]++;	}		f[L+1]=L+1;	for (int i=L; i>=1; i--)	{		int k=min(f[i+1],i+1);		for ( ;k>1 && sum[i]-sum[k-2]<=n; k--) ;		f[i]=k;	}		for (int i=1; i<=N; i++)	{		int l=tag[i]-step[i]+1,r=tag[i]-step[pre[i]];		if (f[tag[i]]>l) l=f[tag[i]];		if (l<=r) ans+=r-l+1;	}	printf("%d\n",ans);	return 0;}

　　


联系
我们