zxx 的题单来的（
发一个无脑 kmp 自动机 + dp 做法。
看到题就很 dp，考虑设计状态。显然填字母时要知道当前串与 \(s,t\) 的匹配位数，否则就不知道 \(s,t\) 是否完整出现。设 \(f_{i,j,k}\) 表示填到 \(c\) 的第 \(i\) 个字符，与 \(s\) 匹配 \(j\) 位，与 \(t\) 匹配 \(k\) 位。转移可以枚举下一位填的字母。
发现我们需要求出某个串的前 \(i\) 位后接一个字符的匹配位数，这不就是 kmp 自动机干的事情吗。。。于是对 \(s,t\) 建 kmp 自动机，转移就很简单了，大概是 \(f_{i,j',k'} \gets f_{i,j,k} + [j'=|s|] - [k'=|t|]\)。
时间复杂度 \(O(26|c||s||t|)\)。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1010;
const int maxm = 55;
int n, m1, m2, f[maxn][maxm][maxm];
int nxt1[maxn][26], nxt2[maxn][26];
char s[maxn], a[maxn], b[maxn];
void solve() {
scanf("%s%s%s", s + 1, a + 1, b + 1);
n = strlen(s + 1);
m1 = strlen(a + 1);
m2 = strlen(b + 1);
for (int i = 1, j = 0; i <= m1; ++i) {
j = nxt1[j][a[i] - 'a'];
nxt1[i - 1][a[i] - 'a'] = i;
for (int k = 0; k < 26; ++k) {
nxt1[i][k] = nxt1[j][k];
}
}
for (int i = 1, j = 0; i <= m2; ++i) {
j = nxt2[j][b[i] - 'a'];
nxt2[i - 1][b[i] - 'a'] = i;
for (int k = 0; k < 26; ++k) {
nxt2[i][k] = nxt2[j][k];
}
}
mems(f, -0x3f);
f[0][0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m1; ++j) {
for (int k = 0; k <= m2; ++k) {
if (f[i - 1][j][k] < -1e9) {
continue;
}
for (char ch = (s[i] == '*' ? 'a' : s[i]); ch <= (s[i] == '*' ? 'z' : s[i]); ++ch) {
int nj = nxt1[j][ch - 'a'], nk = nxt2[k][ch - 'a'];
f[i][nj][nk] = max(f[i][nj][nk], f[i - 1][j][k] + (nj == m1) - (nk == m2));
}
}
}
}
int ans = -1e9;
for (int i = 0; i <= m1; ++i) {
for (int j = 0; j <= m2; ++j) {
ans = max(ans, f[n][i][j]);
}
}
printf("%d\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}