题目传送门

　　传送点I

　　传送点II

　　传送点III

题目大意

　　给定一个字符串$s$，和一个字符串$t$，$t$只包含小写字母，$s$包含小写字母和通配符'?'。询问$t$可能在$s$中出现最多多少次。

 /**

  * Codeforces

  * Problem#808G

  * Accepted

  * Time: 46ms

  * Memory: 1400k

  */

 #include <bits/stdc++.h>

 using namespace std;

 typedef bool boolean;

 const int N = 1e5 + ;

 int n, m;

 char S[N], T[N];

 inline void init() {

     scanf("%s%s", S + , T + );

     n = strlen(S + );

     m = strlen(T + );

 }

 int fail[N];

 void kmp() {

     fail[] = fail[] = ;

     for (int i = , j; i <= m; i++) {

         j = fail[i];

         while (j && T[i + ] != T[j + ])

             j = fail[j];

         fail[i + ] = ((T[i + ] == T[j + ]) ? (j + ) : ());

     }

 }

 boolean match(char *str) {

     for (int i = ; i <= m; i++)

         if (str[i] != T[i] && str[i] != '?')

             return false;

     return true;

 }

 int f[N], g[N];    // f: maximum match times when ends at i, g: maximum match times when ends before i ant at i.

 inline void solve() {

     kmp();

     for (int i = m; i <= n; i++) {

         if (match(S + (i - m))) {

             f[i] = max(f[i], g[i - m] + );

             for (int j = fail[m]; j; j = fail[j])

                 f[i] = max(f[i], f[i - m + j] + );

         }

         g[i] = max(f[i], g[i - ]);

     }

     printf("%d\n", g[n]);

 }

 int main() {

     init();

     solve();

     return ;

 }