Codeforces 808G Anthem of Berland（KMP+基础DP）

题意

给定一个字符串 \(s\) ，一个字符串 \(t\) ，其中 \(s\) 包含小写字母和 "?" ，\(t\) 只包含小写字母，现在把 \(s\) 中的问号替换成任意的小写字母，求 \(t\) 最多在 \(s\) 中出现多少次，\(t\) 可以互相覆盖。

\(1 \leq |s| \leq 10^5\)

\(1 \leq |t| \leq 10^5\)

\(1 \leq |s|\cdot|t| \leq 10^7\)

思路

由于 \(|s|\cdot|t| \leq 10^7\) ，那么用 \(dp[i][j]\) 表示 \(s\) 匹配到第 \(i\) 位，\(t\) 匹配到第 \(j\) 位时的最多出现次数，如果出现"?"，就枚举是哪个字符。需要预处理出在哪一位遇到什么字符，接下来要到哪里匹配的信息。

我们设 \(F[i][j]\) 为匹配到模式串 \(P\) 的第 \(i\) 位，遇到 \(j\) 字符，下一位应该匹配 \(P\) 的哪一位。这个数组可以和 \(f\) 数组一起交替处理，使两者复杂度都得到保证。这个数组的思想也很重要，在后面的 \(\text{AC}\) 自动机中也有体现。

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

typedef long long LL;

using namespace std;

const int N=1e5+5;

const int NN=2e7+5;

char T[N],P[N];

int f[N],F[N][30];	//F[i][j]表示匹配到第i位为'a'+j，下一位应匹配哪一位

int dp[NN];

int n,m;

#define dp(i,j) dp[(i)*(m+5)+j]

int main()

{

	scanf("%s%s",T+1,P+1);

	n=strlen(T+1),m=strlen(P+1);

	f[1]=f[2]=1;FOR(i,0,25)F[1][i]=1+(P[1]-'a'==i);

	FOR(i,2,m)

	{

		f[i+1]=F[f[i]][P[i]-'a'];

		FOR(j,0,25)

		{

			if(P[i]-'a'==j)F[i][j]=i+1;

			else F[i][j]=F[f[i]][j];

		}

	}

	FOR(i,1,n+1)FOR(j,1,m+1)dp(i,j)=-1;

	dp(1,1)=0;

	FOR(i,1,n)FOR(j,1,m)if(~dp(i,j))

	{

		if(T[i]!='?')

		{

			int J=F[j][T[i]-'a'];

			if(J==m+1)dp(i+1,f[J])=max(dp(i+1,f[J]),dp(i,j)+1);

			else dp(i+1,J)=max(dp(i+1,J),dp(i,j));

		}

		else

		{

			FOR(k,0,25)

			{

				int J=F[j][k];

				if(J==m+1)dp(i+1,f[J])=max(dp(i+1,f[J]),dp(i,j)+1);

				else dp(i+1,J)=max(dp(i+1,J),dp(i,j));

			}

		}

	}

	int ans=0;

	FOR(i,1,m)ans=max(ans,dp(n+1,i));

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

	return 0;

}

巴特西

Codeforces 808G Anthem of Berland（KMP+基础DP）

题意

思路

代码

最新文章

热门文章