题解 CF223B 【Two Strings】
littlejuruo
·
·
题解
写在前面
可能更好的阅读体验
麻烦审核的管理员注意一下,把这题错误的翻译改掉,已经不少人被翻译坑了.
提供一下自己的翻译
给你两个字符串s,t,判断是否满足对于每一个s_i,都存在s的子序列x,使s_i \in x且x=t
Translated by littlejuruo
Solution
对于每个位置,我们记录l_i表示s_{1...i}的所有子序列所能匹配t的最长前缀,r_i表示s_{i...|s|}的所有子序列所能匹配t的最长后缀.
那么易得当且仅当r_i \le l_i,我们能找到一个符合要求的子序列包含s_i
那么如何求出l,r呢?
以求l为例,我们用pos_c记录字符c目前的最长前缀,k表示前一个位置匹配的最长前缀,显然k不减,因此我们只需要考虑s_i和t_k是否相等,如果相等,就更新pos和k
l_i$就等于$pos_{s_i}
# Code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10,INF=0x3f3f3f3f;
void file(string s){freopen((s+".in").c_str(),"r",stdin),freopen((s+".out").c_str(),"w",stdout);}
int read(){
int f=1,a=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
a=a*10+ch-'0';
ch=getchar();
}
return a*f;
}
string s,t;
int l[MAXN],r[MAXN],pos[35];
void makel(){
int k=0;
memset(pos,-1,sizeof(pos));
for(int i=0;i<s.length();++i){
if(k<t.length()&&s[i]==t[k]){
l[i]=k,pos[s[i]-'a']=k++;
}else{
l[i]=pos[s[i]-'a'];
}
}
}
void maker(){
int k=t.length()-1;
memset(pos,INF,sizeof(pos));
for(int i=s.length()-1;i>=0;--i){
if(k>=0&&s[i]==t[k]){
r[i]=k,pos[s[i]-'a']=k--;
}else{
r[i]=pos[s[i]-'a'];
}
}
}
signed main(){
// file("");
cin>>s>>t;
makel();
maker();
for(int i=0;i<s.length();++i){
if(l[i]<r[i]){
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}
```