题目描述
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.
输入描述
The first line contains the integer $T$ $(1≤T≤100)$ — the number of test cases.
The first line of each testcase contains one string $s$ $(1≤|s|≤105)$ consisting of lowercase Latin letters.
The second line of each testcase contains one string $t$ $(1≤|t|≤105)$ consisting of lowercase Latin letters.
输出描述
For each testcase, print one integer — the minimum number of operations to turn string z into string t. If it’s impossible print −1.
思路分析
给你两个串s和t，问最小需要几个s中的子序列可以组成t。
有种做法。
一是序列自动机：
- 预处理出nex[i][j]数组，表示i之后第一次出现j的位置。
- 然后暴力匹配就行了。
二是二分查找：
- 将26个字母的位置存进26个数组中。
- 位置肯定是有序的，所以可以二分。
- 也是暴力匹配就行了。
样例输入
3
aabce
ace
abacaba
aax
ty
yyt
样例输出
1
-1
3
二分代码
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int N=1e5+10;
char s[N],t[N];
int main() {
#ifdef xiaofan
freopen("in.txt","r",stdin);
#endif
int T;
cin>>T;
while(T--) {
int vis[26]= {0};
vector<int>q[26];
scanf("%s%s",s,t);
int n=strlen(s),m=strlen(t);
for(int i=0; i<m; i++) {
vis[t[i]-'a']=1;
}
for(int i=0; i<n; i++) {
vis[s[i]-'a']=0;
q[s[i]-'a'].pb(i);
}
int f=0;
for(int i=0; i<26; i++) {
if(vis[i]==1) {
f=1;
break;
}
}
if(f) {
puts("-1");
continue;
}
int ans=1,p=0,idx=-1;
while(p!=m) {
int x=t[p]-'a';
int nx=upper_bound(q[x].begin(),q[x].end(),idx)-q[x].begin();
if(nx==q[x].size()){
ans++;
idx=-1;
}else{
p++;
idx=q[x][nx];
}
}
cout<<ans<<endl;
}
return 0;
}
序列自动机代码
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int N=1e5+10;
char s[N],t[N];
int nex[N][26];
int main() {
#ifdef xiaofan
freopen("in.txt","r",stdin);
#endif
int T;
cin>>T;
while(T--) {
int vis[26]= {0};
scanf("%s%s",s+1,t+1);
int n=strlen(s+1),m=strlen(t+1);
for(int i=1; i<=m; i++)
vis[t[i]-'a']=1;
for(int i=1; i<=n; i++)
vis[s[i]-'a']=0;
int f=0;
for(int i=0; i<26; i++) {
if(vis[i]==1) {
f=1;
break;
}
}
if(f) {
puts("-1");
continue;
}
for(int i=0; i<26; i++)
nex[n][i]=0;
for(int i=n; i>=1; i--) {
for(int j=0; j<26; j++) {
nex[i-1][j]=nex[i][j];
}
nex[i-1][s[i]-'a']=i;
}
int ans=1,pos=0;
for(int i=1; i<=m; i++) {
pos=nex[pos][t[i]-'a'];
if(!pos) {
ans++;
i--;
pos=0;
}
}
cout<<ans<<endl;
}
return 0;
}
