牛客練習賽17 B-好位置

NO IMAGE

連結:https://www.nowcoder.com/acm/contest/109/B
來源:牛客網

題目描述

給出兩個串s和x
定義s中的某一位i為好的位置,當且僅當存在s的子序列 滿足y=x且存在j使得i=kj成立。
問s中是否所有的位置都是好的位置。

輸入描述:

一行兩個字串s,x,這兩個串均由小寫字母構成。
1 <= |s|, |x| <= 200000

輸出描述:

Yes表示是。

No表示不是。

題解:
a1[i]記錄前i個字元(必須包括第i個字元)的最長匹配子序列,
a2[i]記錄後i到最後的最長匹配子序列(可以不包括第i個)。
若a1[i] a2[i 1]>=len,a1[i]>0則i位置一定符合條件。
程式碼:
#include<bits/stdc  .h>
using namespace std;
const int maxn=200005;
int a1[maxn],a2[maxn],f[28];
char t1[maxn],t2[maxn];
int main()
{
scanf("%s%s",t1 1,t2 1);
int len1=strlen(t1 1);
int len2=strlen(t2 1);
int id=1,ans=0;
for(int i=1;i<=len1;i  )
{
if(t1[i]==t2[id])
{
id  ;ans  ;
a1[i]=ans;
f[t1[i]-'a']=ans;
}
else
{
a1[i]=f[t1[i]-'a'];
}
}
id=len2,ans=0;
for(int i=len1;i>=1;i--)
{
if(t1[i]==t2[id])
{
id--,ans  ;
a2[i]=ans;
}
else a2[i]=ans;
}
if(len2>len1)printf("No\n");
else
{
bool bb=1;
for(int i=1;i<=len1;i  )
{
if(a1[i] a2[i 1]>=len2&&a1[i])continue;
bb=0;
}
if(bb)printf("Yes\n");
else printf("No\n");
}
return 0;
}