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; }