【題解】Codeforces 1295C. Obtain The String

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int T, now, nxt, ch, ans;
string s, t;
bool flag;
vector <int> v[26];
 
int main() {
    cin >> T;
    while (T--){
        cin >> s;
        cin >> t;
        for (int i = 0; i < 26; i++){
            v[i].clear();
        }
        for (int i = 0; i < s.length(); i++){
            v[s[i]-'a'].push_back(i); //紀錄字串s中每個字母出現的序位
        }
        now = 0;
        ans = 1;
        flag = true;
        for (int i = 0; i < t.length(); i++){
            ch = t[i]-'a'; //待檢查的字母，轉換成編號(0~25)
            nxt = lower_bound(v[ch].begin(), v[ch].end(), now) - v[ch].begin();
            if (nxt == v[ch].size()){
                if (v[ch].empty()){
                    flag = false; // 字母ch不存在字串s中
                    cout << -1 << "\n";
                    break;
                } else {
                    now = 0; //目前的subsequence已經不敷使用
                    nxt = lower_bound(v[ch].begin(), v[ch].end(), now) - v[ch].begin();
                    ans++; //再多串接一個字串s
                }
            }
            now = v[ch][nxt]+1; //下一個合法的序位
        }
        if (flag) cout << ans << "\n";
    }
}