はまやんはまやんはまやん

hamayanhamayan's blog

Unique Subsequence [APCP2017 Day3 C]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day3&pid=C

解法

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2539812&cid=ACPC2017Day3

前と後ろから貪欲にマッチングをしていって、一致したらyes
しなかったらno

string T, P;
int NT, NP;
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> T >> P;
    NT = T.length(), NP = P.length();
 
    int p = 0;
    deque<int> qu;
    rep(i, 0, NT) {
        if (T[i] == P[p]) {
            p++;
            qu.push_back(i);
            if (p == NP) break;
        }
    }
    if (p != NP) {
        printf("no\n");
        return;
    }
 
    p = NP - 1;
    rrep(i, NT - 1, 0) {
        if (T[i] == P[p]) {
            int pre = qu.back(); qu.pop_back();
            if (pre != i) {
                printf("no\n");
                return;
            }
            p--;
            if (p < 0) break;
        }
    }
    if (0 <= p) {
        printf("no\n");
        return;
    }
 
    printf("yes\n");
}