CF 1295——C.Obtain The String【二分】

题目传送门

You are given two strings s and t consisting of lowercase Latin letters. Also you have a string z which is initially empty. You want string z to be equal to string t. You can perform the following operation to achieve this: append any subsequence of s at the end of string z. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if $z=ac,s=abcde$, you may turn z into following strings in one operation:

$z=acace$ (if we choose subsequence ace);
$z=acbcd$ (if we choose subsequence bcd);
$z=acbce$ (if we choose subsequence bce).
Note that after this operation string s doesn’t change.

Calculate the minimum number of such operations to turn string z into string t.

Input

The first line contains the integer $T(1\le T\le 100)$ — the number of test cases.

The first line of each testcase contains one string $s(1\le |s|\le 10^5)$ consisting of lowercase Latin letters.

The second line of each testcase contains one string $t(1\le |t|\le 10^5)$ consisting of lowercase Latin letters.

It is guaranteed that the total length of all strings s and t in the input does not exceed $2?10^5$.

Output

For each testcase, print one integer — the minimum number of operations to turn string z into string t. If it’s impossible print ?1.

input

3
aabce
ace
abacaba
aax
ty
yyt

output

1
-1
3

题意

• 给定两个字符串s和t，你有一个空字符串z

• 每次可以取s的任意一个子序列加到z后面

• 问至少要取多少次才能让z等价于t

题解

• vector存s中26个字母的位置

  然后字符串$t$从前往后一个个查找

  用变量p记录查到上一个字符时在字符串s中的位置（初始化为-1）

  如果在t内碰到一个字符，没有在s中出现过，输出-1结束当次程序

  否则，看当前的p是否大于等于这个字符在s中出现的最后一个位置

  如果是，说明这一次子序列已经不能往后面取了，说明得另起一次从头取子序列

  ans++，让p等于当前字符在s中出现的第一个位置

  如果不是二分找大于p的第一个这个字符的位置，让p等于这个位置即可

• 注意，ans初始化为1，vector要清空……

  思路用到了一点点贪心，就是每次都是取上一次的位置后出现的第一个指定字符的位置

  反正正常模拟肯定超时要二分优化，嗯！

AC-Code

#include <bits/stdc++.h>
using namespace std;vector<int>vec[26];
int num[26];
int main() {
    int T;cin >> T;while (T--) {
    memset(num, 0, sizeof num);for (int i = 0; i < 26; ++i)vec[i].clear();string s, t;cin >> s >> t;for (int i = 0; i < s.length(); ++i) {
    vec[s[i] - 'a'].push_back(i);++num[s[i] - 'a'];}int ans = 1;int p = -1;for (int i = 0; i < t.length(); ++i) {
    if (!num[t[i] - 'a']) {
    ans = -1;break;}else if (p >= vec[t[i] - 'a'][num[t[i] - 'a'] - 1]) {
    ++ans;p = vec[t[i] - 'a'][0];}else p = vec[t[i] - 'a'][upper_bound(vec[t[i] - 'a'].begin(), vec[t[i] - 'a'].end(), p) - vec[t[i] - 'a'].begin()];}cout << ans << endl;}return 0;
}