We say two characters \(a\) and \(b\) match if \(a=b\) or at least one is ?. Then two strings \(S\) and \(R\) match if and only if the \(i\)-th characters of \(S\) and \(T\) match for all \(i=1,2,\ldots,|S|\).

Furthermore, for each \(x\), \(S'\) and \(T\) match if and only if each of the first \(x\) characters of \(S\) and \(T\) match respectively and each of the last \((|T|-x)\) characters of \(S\) and \(T\) match respectively. Thus, by preparing an array \(\mathrm{pre}_i\) that represents whether the first \(i\) characters of \(S\) and \(T\) match, and another array \(\mathrm{suf}_i\) that represents whether the last \(i\) characters of \(S\) and \(T\) match, we can answer for each of \(x=0,1,2,\ldots,|T|\) in an \(\mathrm{O}(1)\) time each.

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

bool match_or_not(char a,char b){
	return a=='?' || b=='?' || a==b;
}

int main() {
    
	string S,T;
	cin>>S>>T;
	
	vector<int> pre(S.size()+1,false),suf(S.size()+1,false);
	
	pre[0] = true;
	for(int i=0;i<T.size();i++){
		if(!match_or_not(S[i],T[i]))break;
		pre[i+1] = true;
	}
	
	reverse(S.begin(),S.end());
	reverse(T.begin(),T.end());
	
	suf[0] = true;
	for(int i=0;i<T.size();i++){
		if(!match_or_not(S[i],T[i]))break;
		suf[i+1] = true;
	}
	
	for(int i=0;i<=T.size();i++){
		if(pre[i] && suf[T.size()-i])printf("Yes\n");
		else printf("No\n");
	}
	
	return 0;
}