C - Obtain The String
题意
给出s串 和目标串t
你可以从s串中取出任意子序列拼接
问最少取出几个子序列才能拼出目标串t
题解
发现 如果t串某个字母需要取到 t上一个字母在s串中取得字符的位置之前
那么结果就需要增加一个子序列产能拼接出t
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| # include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define IO std::ios::sync_with_stdio(false);
# define endl '\n'
string s,t;
const int maxn=(int)1e6+5;
int first[30];
int have[30][(int)1e5+5];
int main() {
int T;cin>>T;
while(T--){
cin>>s>>t;
int lens=s.size();
for(int i=0;i<30;i++)first[i]=-1;
for(int i=0;i<lens;i++){
if(first[s[i]-'a']==-1)first[s[i]-'a']=i;
for(int j=0;j<30;j++)have[j][i]=maxn;
}
for(int i=0;i<30;i++)have[i][lens]=maxn;
for(int i=lens-1;i>=0;i--){
have[s[i]-'a'][i]=i;
for(int j=0;j<30;j++){
have[j][i]=min(have[j][i],have[j][i+1]);
}
}
int lent=t.size();int per=-1,ans=1;bool flag=1;
for(int i=0;i<lent;i++){
if(first[t[i]-'a']==-1){flag=0;break;}
bool vis=0;
if(first[t[i]-'a']<=per&&have[t[i]-'a'][per+1]==maxn)ans++,vis=1;
if(vis)per=first[t[i]-'a'];
else per=have[t[i]-'a'][per+1];
}
if(flag)cout<<ans<<endl;
else cout<<-1<<endl;
}
}
|