CF223B Two Strings 题解

题意

题目链接

询问是否:对于 $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;
}
本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇