CF223B Two Strings 题解

发布于 2021-02-02  478 次阅读


题意

题目链接

询问是否:对于 $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;
}

月流华 岁遗沙 万古吴钩出玉匣