当前位置:网站首页>CodeForces 808G Anthem of Berland 前缀函数 KMP DP

CodeForces 808G Anthem of Berland 前缀函数 KMP DP

2021-02-20 19:59:41 _int_me

原题链接

题意


  • 第一行给我们一串长为s,只包含小写字母与问号的字符串A,第二行给我们一个长为t只有小写字母的字符串B, 同时满足 $ s * t \le 1e7 $

  • 我们可以把问号变成任意的字母,我们需要求出如何变换才能使A串包含最多次B串(可以重叠),输出这个最大值

思路


  • 单模式串匹配我们可以想到KMP算法或者前缀函数

  • 一开始贪心考虑将“?”设置为100%匹配,但是显然这是行不通的,比如下面这组数据

\[acc??cca \\ acca \]

显然答案是2,A应该变成如果kmp算法来贪心匹配,到第二个问号的时候,会将?设置为c,那么就和正确结果不符了

  • 因为两字符串长度乘积最多为一千万,所以可以考虑DP,我们先预处理出B串的前缀函数值,然后给B串添加一个分隔符#之后,处理出前缀函数的自动机

\[prem[i][j] \]

也就是在当前前缀函数值为i的情况下,下一个字符为j时转移到的前缀函数值。

  • 这样我们设置DP数组

\[dp[i][j] \]

为当前在A串的i位置,匹配到B串的j位置时(也就是前缀函数为j)的最大匹配数。为了便于理解我们初始化dp[0][0]为0,其他值为-1,转移方程为

\[dp[i][prem[j][k]] = max_{'a' \le k \le 'z'}\{max_{0 \le j \le t}\{dp[i - 1][j] + (prem[j][k] == t)\}\} (A[i] = '?') \\ dp[i][prem[j][A[i]]] = max_{0 \le j \le t}\{dp[i - 1][j] + (prem[j][A[i]] == t)\} (A[i] \ne '?') \]


  • 最后取dp[s][i]中的最大值即可,对于空间问题,可以将两维写在一维中,或者使用滚动数组

AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100000;

char ss[N + 5], sss[N + 5];
int prem[N + 5][26];
int pf[N + 5];
int dp[2][N + 5];
int len;

void prefun(char *s)
{
	len = strlen(s + 1);
	pf[0] = pf[1] = 0;
	for (int i = 2; i <= len; ++i)
	{
		pf[i] = 0;
		int l = pf[i - 1];
		while (l && s[l + 1] != s[i])
		{
			l = pf[l];
		}
		if (s[l + 1] == s[i])
		{
			pf[i] = l + 1;
		}
	}
}

void preatm(char *s)
{
	s[++len] = '#';
	for (int i = 0; i < len; ++i)
	{
		for (int j = 0; j < 26; ++j)
		{
			if (i && 'a' + j != s[i + 1])
			{
				prem[i][j] = prem[pf[i]][j];
			}
			else
			{
				prem[i][j] = i + ('a' + j == s[i + 1]);
			}
		}
	}
}

int main()
{
	scanf("%s%s", ss + 1, sss + 1);
	memset(dp, -1, sizeof(dp));
	prefun(sss);
	preatm(sss);
	dp[0][0] = 0;
	int len2 = strlen(ss + 1);
	for (int i = 1; ss[i]; ++i)
	{
		if (ss[i] == '?')
		{
			for (int j = 0; j < len; ++j)
			{
				if (dp[1 - i % 2][j] != -1)
				{
					for (int k = 0; k < 26; ++k)
					{
						dp[i % 2][prem[j][k]] = max(dp[1 - i % 2][j] + (prem[j][k] == len - 1), dp[i % 2][prem[j][k]]);
					}
				}
			}
		}
		else
		{
			for (int j = 0; j < len; ++j)
			{
				if (dp[1 - i % 2][j] != -1)
				{
					dp[i % 2][prem[j][ss[i] - 'a']] = max(dp[1 - i % 2][j] + (prem[j][ss[i] - 'a'] == len - 1), dp[i % 2][prem[j][ss[i] - 'a']]);
				}
			}
		}
		for (int j = 0; j < len; ++j)
		{
			dp[1 - i % 2][j] = -1;
		}
	}
	int ans = 0;
	for (int i = 0; i < len; ++i)
	{
		ans = max(ans, dp[len2 % 2][i]);
	}
	printf("%d\n", ans);
	return 0;
}

版权声明
本文为[_int_me]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/int-me-X/p/14423030.html