AtCoder Beginner Contest 287 D - Match or Not

この問題では「SとTが前から何番目まで一致しているか」と「SとTが後ろから何番目まで一致しているか」 を先に調べることによってO(N)で問題を解くことができます。

例えば aaabbbccc と a?a?b?c の場合

前から調べると

T	T	T	T	T	T	T
a	a	a	b	b	b	c	c	c
a	?	a	?	b	?	c

後ろから調べると

						F	T	T
a	a	a	b	b	b	c	c	c
		a	?	a	?	b	?	c

後ろから3文字目がマッチしないため それ以降はFとします。

		F	F	F	F	F	T	T
a	a	a	b	b	b	c	c	c
		a	?	a	?	b	?	c

前からのboolを保存する配列 front_matchと 後ろからのboolを保存する配列 rear_matchを作ります 長さはT+1としてindex0はTとしておきます。 こうすることによってx=0のときは
front_match[0], rear_match[T.length()]
x = 1のときは
front_match[1], rear_match[T.length()-1]
のandをとることによって TならばYes
FならばNo
と判断することができます。

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

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


int main() {
    string S, T;
    cin >> S >> T;
    vector<bool> front_match(T.length()+1, false), rear_match(T.length()+1, false);

    front_match[0] = true;
    for (int i = 0; i <= T.length(); i++) {
        if (!is_match(S[i], T[i])) break;
        front_match[i+1] = true;   
    }

    reverse(S.begin(),S.end());
    reverse(T.begin(),T.end());

    rear_match[0] = true;
    for (int i = 0; i <= T.length(); i++) {
        if (!is_match(S[i], T[i])) break;
        rear_match[i+1] = true;   
    }

    for (int i = 0; i <= T.length(); i++) {
        if (front_match[i] && rear_match[T.length()-i]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}