题解：CF223B Two Strings
StarsIntoSea
·
·
题解
水。
设 f(i) 表示 s 的前 i 个字符中，存在等于 t_{[1,f(i)]} 的最长子序列。
然后枚举 $s$ 中的位置 $1 \le i \le |s|$，这个字符放在 $t$ 中的某一个位置 $j$，如果满足 $f(i-1) \ge j-1,g(i+1) \ge |t| - j$，那么这个位置就是符合条件的，否则就不符合。
但是直接枚举 $j$ 是平方的，因为考虑 $f(i-1)$ 和 $g(i+1)$ 的取值并放在 $t$ 上考虑。即考虑 $t$ 上的区间 $[|t|-g(i-1),f(i-1)+1]$。若区间合法并且该区间内有等于 $s_i$ 的字符则符合条件，否则不符合。
至于怎么找区间内有没有对应的字符，前缀和即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
char s[N],t[N];
int f[N],g[N];
int sum[N][28];
int main(){
scanf("%s",s+1);
scanf("%s",t+1);
int n=strlen(s+1),m=strlen(t+1);
int j=1; f[1]=0;
for(int i=1;i<=n;++i){
f[i]=f[i-1];
if(s[i]==t[j] && j<=m) f[i]++,j++;
}
g[n+1]=0; j=m;
for(int i=n;i>=1;i--){
g[i]=g[i+1];
if(s[i]==t[j] && j>=1) g[i]++,j--;
}
for(int i=1;i<=m;++i) sum[i][t[i]-'a']++;
for(int j=0;j<26;++j)
for(int i=1;i<=m+1;++i)
sum[i][j]+=sum[i-1][j];
for(int i=1;i<=n;++i){
int l=m-g[i+1],r=f[i-1]+1;
if(l>r || sum[r][s[i]-'a']-sum[max(l-1,0)][s[i]-'a']==0){
printf("No"); return 0;
}
}
printf("Yes\n");
}
```