算法

(贪心、二分)

对于子列判定问题，我们一般可以贪心地去匹配。即，判断字符串 $t$ 是否为字符串 $u$ 的子列，我们可以先找 $t$ 的第一个字母在 $u$ 中第一次出现的位置，在第一次匹配之后我们再找 $t$ 的第二个字母在 $u$ 中匹配的位置，…，直到判定完 $t$ 中最后一个字母也能在 $u$ 中匹配。对此，我们可以每次找 $t$ 中的字母在位置 $i$ 之后第一次出现的位置，用二分来实现会比较方便。

虽然 $s’$ 是无限长的，但是 $t$ 的长度是有限的，所以对 $|t|$ 的每一个操作进行一次就足够了，上面提到的操作足够快。
注意这里到只需对 $s$ 复制两次即可，对于在 $s’$ 中匹配到的位置 $p$ 若大于等于 $n$，我们可以把 $p$ 减掉 $n$，同时把 $n$ 累加进答案里。为何不能只复制一遍？显然不行，因为 $t$ 的后面字母可能在 $s$ 中匹配不到。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;

int main() {
    string s, t;
    cin >> s >> t;

    int n = sz(s), m = sz(t);
    vector<vector<int>> is(26);
    rep(i, n) is[s[i] - 'a'].push_back(i);
    rep(i, n) is[s[i] - 'a'].push_back(i + n);

    ll ans = 0;
    int p = 0;
    rep(i, m) {
        int c = t[i] - 'a';
        if (sz(is[c]) == 0) {
            puts("-1");
            return 0;
        }
        p = *lower_bound(is[c].begin(), is[c].end(), p) + 1;
        if (p >= n) {
            p -= n;
            ans += n;
        }
    }

    ans += p;
    cout << ans << '\n';

    return 0;
}