Codeforces 1163D（kmp、dp）

要点

• \(dp[i][j][k]\)表示主串已经到第\(i\)位时，\(s\)匹配在\(j\)位、\(t\)匹配在\(k\)位的最大得分
• 本来就要试填一层循环，如果转移也写在循环里的化复杂度承受不了，于是开两个表kmp预处理一下。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

char ch[1010], s[55], t[55];

int len, ls, lt, Ns[55], Nt[55];

int Ps[55][30], Pt[55][30];

int dp[1010][55][55], ans = 0xcfcfcfcf;

void GetNext(char *s, int len, int *Next, int P[][30]) {

	Next[1] = 0;

	for (int i = 2, j = 0; i <= len; i++) {

		while (j && s[j + 1] != s[i])	j = Next[j];

		if (s[i] == s[j + 1])	j++;

		Next[i] = j;

	}

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

		for (int c = 0; c < 26; c++) {

			int j = i;

			while (j && s[j + 1] != c + 'a')	j = Next[j];

			if (s[j + 1] == c + 'a')	j++;

			P[i][c] = j;

		}

}

int main() {

	scanf("%s%s%s", ch + 1, s + 1, t + 1);

	len = strlen(ch + 1), ls = strlen(s + 1), lt = strlen(t + 1);

	GetNext(s, ls, Ns, Ps), GetNext(t, lt, Nt, Pt);

	memset(dp, 0xcf, sizeof dp);

	dp[0][0][0] = 0;

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

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

			for (int k = 0; k <= lt; k++)

				for (int c = 0; c < 26; c++) {

					if (ch[i + 1] != '*' && ch[i + 1] - 'a' != c)	continue;

					if (dp[i][j][k] == 0xcfcfcfcf)	continue;

					int a = Ps[j][c], b = Pt[k][c];

					dp[i + 1][a][b] = max(dp[i + 1][a][b], dp[i][j][k] + (a == ls) - (b == lt));

				}

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

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

			ans = max(ans, dp[len][i][j]);

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

}