808g.cpp

#include <bits/stdc++.h>
#define MAXN 200000
#define debug_arr(arr, n) cerr << #arr << " = "; for (int i=0;i<n;i++) cout << arr[i] << " \n"[i == n-1]
using namespace std;

string frase, grande, pequena;
int n, m, back[MAXN];

vector < vector <int> > dp;

// aba??
// aba
// 001 

void kmp(){
	for (int i=1, j; i<m; i++){
		j = back[i-1];
		while (j > 0 && pequena[i] != pequena[j]) j = back[j-1];
		if (pequena[i] == pequena[j]) j++;
		back[i] = j;
	}
	debug_arr(back, m);
}


int solve(int p, int g){
	cout << p << " " << g << endl;
	if (dp[p][g] != -1) return dp[p][g];
	if (g > n) return dp[p][g] = 0;

	dp[p][g] = 0;

	if (p < m && (grande[g] == pequena[p] || grande[g] == '?')){
		return dp[p][g] = solve(p + 1, g + 1);
	}

	int j = p;
	while (j > 0){
		j = back[j-1];
		dp[p][g] = max(dp[p][g], solve(j, g + 1)) + (p == m);
	}
	dp[p][g] = max(dp[p][g], solve(0, g + 1));

	return dp[p][g];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> grande >> pequena;


	n = grande.size();
	m = pequena.size();
	kmp();

	for(int i = 0; i < m + 4; i++){
		dp.push_back(vector<int>());
		for(int j = 0; j < n + 4; j++){
			dp[i].push_back(-1);
		}
	}

	cout << solve(0, 0) << endl;
	return 0;
}