本题我采用了序列自动机的方法,设置一个nxt[MAXLEN][30]数组,此数组的行与字符串母串的字符一一对应,列代表26个英文字母,nxt[i][j]=0表示字符'a'+j
在字符t[i]后不存在,nxt[i][j] > 0,其数值表示字符'a'+j
在字符t[i]的坐标。
注意:不要使用memset重置子串,会超时,来自于菜鸡的血泪
#include <iostream>
using namespace std;
#include <string.h>
#include <stdlib.h>
const int MAXLEN = 1e6 + 5;
char s[MAXLEN]; //存放输入的字符串母串
int nxt[MAXLEN][26]; //横坐标分别对应字符串s的每一个字符,纵坐标是26个字母,数组存放的是距离当前字符最近的后一个字符的位置
char t[MAXLEN]; //记录字串
int main(void)
{
scanf("%s", s); //从下标1的位置开始输入字符串
int s_len = strlen(s);
//将当前字符串中每个字符所在位置传入next数组
//分别推出每个元素的值
for(int i = s_len-1; i >= 0; i--)
{
nxt[i][s[i]-'a'] = i+1;
for(int j = 0; j < 26; j++)
{
if(0 == nxt[i][j])
nxt[i][j] = nxt[i+1][j];
}
}
int n;
scanf("%d", &n);
while(n--)
{
scanf("%s", t);
int t_len = strlen(t);
int pos = 0; //指向nxt数组的指针
bool flag = true;
//遍历字串,在nxt数组中找对应位置
for(int i = 0; i < t_len; i++)
{
//如果字符找不到
pos = nxt[pos][t[i]-'a'];
if(0 == pos)
{
flag = false;
break;
}
}
if(true == flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}