CODE THANKS FESTIVAL 2015 E - ノイズ除去

問題

code-thanks-festival-2015-open.contest.atcoder.jp

解法

文字列 S の start 以降の部分文字列を使うと, 文字列 T が表現できるとしましょう。このとき, S の start 以降の文字列は, T に現れる文字(例えば T = "abc" だったら a, b, c) を飛ばすことなく, T と一致するような部分文字列を持たなければなりません。
入力例 1 の
abba aba
というのがわかりやすいですが, これは start = 0 からの文字列は b という T に現れる文字を飛ばさないと S の部分文字列に T が出てこないので NG です。

このことに注意しながら S のどの文字からの文字列を考えるかで場合分けして頑張れば OK です。

bool ng[30];

void solve(string s, string t) {
    int n = s.size(), m = t.size();
    memset(ng, false, sizeof(ng));
    for (int i = 0; i < m; i++) ng[t[i]-'a'] = true;
    for (int start = 0; start < n; start++) {
        int cur = 0;
        for (int i = start; i < n; i++) {
            if (s[i] == t[cur]) {
                cur++;
                if (cur == m) break;
            }
            else {
                if (ng[s[i]-'a']) {
                    break;
                }
            }
        }
        if (cur == m) {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while (Q--) {
        string s, t;
        cin >> s >> t;
        solve(s, t);
    }
    return 0;
}