一维数组不好储存先后位置 所以用二维数组nt[i][j]记录当前位置i后面最靠近字母j的位置
后缀一下,从后往前记录 特例由于 nt[i][a[i]-'a']=i; 记录的是它本身的位置
所以后面查找成功后位置加一 d=nt[d][b[j]-'a']+1;否则遇到相同连续字符会一直在该位置上逗留
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e7+7;
string a;
int n;
int nt[maxn][30]={0};
int main()
{
getline(cin,a);
cin>>n;
fill(nt[a.length()]+0,nt[a.length()]+26,-2);///处理边界
for (int i=a.length()-1;i>=0;--i)
{
for (int j=0;j<26;++j)
{
nt[i][j]=nt[i+1][j];
}
nt[i][a[i]-'a']=i;
}
while (n--)
{
int d=0;
string b;
bool flag=true;
cin>>b;
for (int j=0; j<b.length();++j)
{
if (nt[d][b[j]-'a']!=-2)///达到边界或者寻找不到该字符位置
{
d=nt[d][b[j]-'a']+1;
}
else
{
flag=false;
break;
}
}
if (flag)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}


京公网安备 11010502036488号