1343: PIPI的字符串问题Ⅰ

使用了序列自动机，next[i][j]表示主串第i个位置及其之后最近的字母j的索引

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N], t[N];
int next1[N][26];
int main(){scanf("%s",s+1);int n = strlen(s+1);for(int i=n;i>0;i--){for(int j=0;j<26;j++)next1[i][j]=next1[i+1][j];next1[i][s[i]-'a']=i;}int q;scanf("%d",&q);while(q--){	scanf("%s",t+1);int len=strlen(t+1);int now=0; //now指向已经找到的字母在s中的索引 for(int i=1;i<=len;i++){now=next1[now+1][t[i]-'a'];if(!now) break;}if(!now)cout<<"No"<<endl;else printf("Yes\n");}return 0;
}