题意
询问是否:对于 $s$ 中每一个 $s_i$,都找的到一个包含它的 $s$ 的子序列(不是子串)与 $t$ 相同。
解析
首先我们考虑,必须要按顺序找到第一个子序列,否则一定是 No
。
例如,若 $t=abcd$,$s$ 的前几项可以为 $aabbbcdd$,但是不能为 $acbcd$,因为第一个 $c$ 一定不满足。
找到之后,我们记录每一个字母在 $t$ 中出现的最后一个位置。为什么是最后一个?因为我们后续找到字符,将他作为子序列中的后面那个位置一定比前面那个位置更容易配对。
例如:若 $t=aba$,我们后续在 $s$ 中找到了一个 $a$,那么记录最后一个位置,相当于将它接到最后去,这个子序列就已经满足了,如果将它作为第一个位置,还需要找到一个 $b$,显然是划不来的。
然后再使用一个指针 $l$,在便历 $s$ 的过程中,用 $l$ 记录下一个需要找的数在 $t$ 中是哪个位置,如果最终 $ l \le length_t$ 的话就说明一定存在某些字母没有配对成功。
如果仍然无法理解,可以结合代码,配有注释。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
char s[N],t[N];
int sn,tn,l=1,cnt=1;
int f[50];
int main(){
scanf("%s%s",s+1,t+1);
sn=strlen(s+1);tn=strlen(t+1);
for(int i=1;i<=sn;i++){
if(s[i]==t[cnt]) f[s[i]-'a']=++cnt;//记录 t 中每一个字母的位置
if(s[i]==t[l]) l++;//如果能接下去,那就接下去
if(f[s[i]-'a']<l) l=f[s[i]-'a'];//发现了一个更前的需要加入子序列的字母
//只能将 l 往前移到这个字母的后面重新准备接下去
if(l<=1){ //如果发现了 t 中不存在的字母,或者第一个子序列接不成功
printf("No\n");//这两种情况中的任意一种都必然是 No
return 0;
}
}
if(l<=tn) printf("No\n");//如果最后边接不上,也是 No
else printf("Yes\n");
return 0;
}