文字 \(a, b\) に対し、\(a=b\) であるか、少なくとも一方が ? であるときに \(a\) と \(b\) がマッチするということにします。すると、文字列 \(S,T\) がマッチするとは \(i=1,2,\ldots,|S|\) に対し \(S\) の \(i\) 文字目と \(T\) の \(i\) 文字目がマッチする、と言い換えられます。

さらに、各 \(x\) について \(S'\) と \(T\) がマッチするというのは「\(S\) の先頭 \(x\) 文字と \(T\) の先頭 \(x\) 文字がそれぞれマッチし、さらに \(S\) の末尾 \(|T|-x\) 文字と \(T\) の末尾 \(|T|-x\) 文字がそれぞれマッチする」と言い換えられます。 そこで、\(\mathrm{pre}_i\) を \(S\) の先頭 \(i\) 文字と \(T\) の先頭 \(i\) 文字がマッチするかどうかを表す配列、\(\mathrm{suf}_i\) を \(S\) の末尾 \(i\) 文字と \(T\) の末尾 \(i\) 文字がマッチするかどうかを表す配列とし、前計算を行う事で\(x=0,1,2,\ldots,|T|\) それぞれに対して \(\mathrm{O}(1)\) で答えることが可能になります。

実装例(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;
}