Strings of Impurity [AtCoder Beginner Contest 138 E]

https://atcoder.jp/contests/abc138/tasks/abc138_e

解説

https://atcoder.jp/contests/abc138/submissions/7015274

文字列tを先頭から貪欲にs'からとっていく。
貪欲にとるためには、文字列sのある場所から一番近いどころにある、とある文字の座標を取ってくる操作が必要である。
これは累積和を使えば実現可能。
具体的には、migi[cu][c] := cu文字目より右にある文字cの座標を作る。
これはA[i] = cであるとき、migi[i - 1][c] = iが言える。
これをすべての文字について行い、chmin(migi[i][c], migi[i - 1][c])として累積和的に更新していけばいい。
自分はStringMasterとしてライブラリ整備してるので、これを使って貪欲にとっていった。

string S, T;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> T;
    fore(c, S) c -= 'a';
    fore(c, T) c -= 'a';
    StringMaster sm(S);

    ll ans = 0;
    int cu = -1;
    rep(i, 0, T.size()) {
        int c = T[i];
        int to = sm.gomigi(cu, c);
        if (cu < 0 and to == inf) {
            cout << -1 << endl;
            return;
        }

        if (to == inf) {
            ans += S.length() - cu - 1;
            cu = -1;
            i--;
            continue;
        }

        ans += to - cu;
        cu = to;
    }
    cout << ans << endl;
}