fold爷出的题，突然想起来了存个板子。。

对串S讨论一下DP就行了 d p [ i ] [ u ] = m a x ( d p [ i − 1 ] [ j ] + v a l [ u ] , d p [ i ] [ u ] ) dp[i][u] = max(dp[i-1][j]+val[u], dp[i][u]) dp[i][u]=max(dp[i−1][j]+val[u],dp[i][u])
注意建fail指针的时候要val[u] += val[fail[u]],一个t串如果包含另外一个t串，要把子串出现的次数加到自己身上。

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
const ll mod = 1e9 + 7;
int Case = 1;
int n, m;
int dp[3][maxn];
struct node {
  int fail[maxn], nex[maxn][26], val[maxn];
  int root, tot;
  int newnode() {
    for (int i = 0; i < 26; i++) nex[tot][i] = 0;
    val[tot] = 0;
    return tot++;
  }
  void init() {
    tot = 0;
    root = newnode();
  }
  void insert(char *s) {
    int len = strlen(s), u = root;
    for (int o = 0; o < len; o++) {
      int ch = s[o] - 'a';
      if (!nex[u][ch]) nex[u][ch] = newnode();
      u = nex[u][ch];
    }
    val[u]++;
  }
  void getfail() {
    queue<int> Q;
    for (int i = 0; i < 26; i++) {
      if (nex[root][i]) {
        fail[nex[root][i]] = root;
        Q.push(nex[root][i]);
      }
    }
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      val[u] += val[fail[u]];
      for (int i = 0; i < 26; i++) {
        if (!nex[u][i])
          nex[u][i] = nex[fail[u]][i];
        else {
          Q.push(nex[u][i]);
          fail[nex[u][i]] = nex[fail[u]][i];
        }
      }
    }
  }
  void query(char *s) {
    int len = strlen(s);
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= len; i++) {
      for (int j = 0; j < tot; j++) dp[i % 2][j] = -1;
      for (int j = 0; j < tot; j++) {
        if (dp[(i - 1) % 2][j] == -1) continue;
        if (s[i - 1] == '?')
          for (int k = 0; k < 26; k++) {
            int u = nex[j][k];
            dp[i % 2][u] = max(dp[(i - 1) % 2][j] + val[u], dp[i % 2][u]);
          }
        else {
          int u = nex[j][s[i - 1] - 'a'];
          dp[i % 2][u] = max(dp[(i - 1) % 2][j] + val[u], dp[i % 2][u]);
        }
      }
    }
    int res = 0;
    for (int i = 0; i < tot; i++) res = max(res, dp[len % 2][i]);
    printf("%d\n", res);
  }
} ac;
char ss[maxn];
char temp[maxn];
void solve() {
    scanf("%s", ss);
    scanf("%d", &n);
  ac.init();
  for (int i = 1; i <= n; i++) {
    scanf("%s", temp);
    ac.insert(temp);
  }
  ac.getfail();
  ac.query(ss);
  return;
}
int main() {
  // g++ -std=c++11 -o2 1.cpp -o f && ./f < in.txt
  // ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt","w",stdout);
#endif
  while (Case--) {
    solve();
  }
  return 0;
}