题意：给你一个字符串s，以及两个字符串s1,s2.s中有些位置是*,意思是可以随便填字母，s的子串中如果出现一次s1,就加一分，如果出现一次s2，就减一分。问这个字符串s最多可以得多少分？
思路：
设dp[i][j][k]为到s串的i位置,s1的匹配长度是i,s2的匹配长度是j的情况下可以获得的最多分数。那么我们需要枚举这一位填什么字符，然后转移到下一个状态，所有以我们需要对s1和s2预处理一个东西：对s1/s2串匹配长度为i，并且i +1位置填的是字符c的时候，转移到的匹配长度，这个需要预处理一下。
代码：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1010;
const int maxm = 55;
char s[maxn], s1[maxm], s2[maxm];
int kmp_s1[maxm], Next_s1[maxm][26], kmp_s2[maxm], Next_s2[maxm][26];
int dp[maxn][55][55];
void init(char s[maxn], int len, int kmp[maxn], int Next[maxn][26]) {
kmp[1] = 0;
for (int i = 2, j = 0; i <= len; i++) {
while(j && s[j + 1] != s[i])j = kmp[j];
if(s[j + 1] == s[i])j++;
kmp[i] = j;
}
for (int i = 0; i <= len; i++) {
for (char c = 'a'; c <= 'z'; c++) {
int now = i;
while(now && s[now + 1] != c) now = kmp[now];
if(s[now + 1] == c) now++;
Next[i][c - 'a'] = now;
}
}
}
int main() {
scanf("%s%s%s", s + 1, s1 + 1, s2 + 1);
int len = strlen(s + 1), n = strlen(s1 + 1), m = strlen(s2 + 1);
init(s1, n, kmp_s1, Next_s1);
init(s2, m, kmp_s2, Next_s2);
memset(dp, 0xcf, sizeof(dp));
dp[0][0][0] = 0;
for (int i = 0; i <= len; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k <= m; k++) {
for (int c = 0; c < 26; c++) {
if(s[i + 1] == 'a' + c || s[i + 1] == '*') {
int tmp1 = Next_s1[j][c], tmp2 = Next_s2[k][c];
int tmp = dp[i][j][k] + (tmp1 == n) - (tmp2 == m);
dp[i + 1][tmp1][tmp2] = max(dp[i + 1][tmp1][tmp2], tmp);
}
}
}
int ans = -INF;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
ans = max(ans, dp[len][i][j]);
printf("%d
", ans);
}