CF223B Two Strings 题解

写在前面

支持一下蒟蒻的洛谷博客

这题在洛谷上的翻译有问题

提供一下自己的翻译

给你两个字符串(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})

(r)也可以用同样的方式求出来,只不过把顺序和初值改一下就行了

Code

#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;
}