Nowcoder contest 392 J (模板题)【序列自动机】

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+5;
int n,m,T;
char str[N],s[N];
int nxt[N][26],pos[26];
 
void init(){     //预处理主串的信息
    n=strlen(str+1);
    for(int i=0;i<26;i++) pos[i]=n+1;    //a~z中每个字母的下一个字母所对应的位置
    for(int i=n;~i;i--){
        for(int j=0;j<26;j++)
            nxt[i][j]=pos[j]; //记录下下一次出现这个字符的位置
        pos[str[i]-‘a‘]=i;    //更新a[i]最对应的字母对应的当前最靠前的位置
    }
}
bool solve(){
    scanf("%s",s+1);
    m=strlen(s+1);int x=0;   //x从0开始，0作为虚根
    for(int i=1;i<=m;i++){
        int v=s[i]-‘a‘;
        if(nxt[x][v]==n+1) return false;    //如果下一个出现字符的位置不存在，则说明该子串并未完全匹配
        x=nxt[x][v];
    } return true;
}
 
int main(){
    scanf("%s",str+1);
    cin>>T;init();
    while(T--) solve()?puts("Yes"):puts("No");
}

#include <bits/stdc++.h>
using namespace std;
 
const int MaxN = 1e6 + 5;
 
int N, L;
char str[MaxN], str2[MaxN];
 
struct SAM {
  int cntv;
  int nxt[MaxN];
  int last[26], ch[26][MaxN];
  SAM() { nxt[0] = -1; }
 
  inline void insert(int c) {
    cntv++; nxt[cntv] = last[c];
    for (int i = 0; i < 26; ++i)
      for (int p = last[i]; p != -1 && ch[c][p] == 0; p = nxt[p])
        ch[c][p] = cntv;
    last[c] = cntv;
  }
 
  inline bool check(int u, int x) {
    if (x == L) return true;
    int c = str2[x] - ‘a‘;
    if (ch[c][u] == 0) return false;
    return check(ch[c][u], x + 1);
  }
} sam;
 
void init() {
  scanf("%s", str);
  scanf("%d", &N);
  for (int i = 0; str[i]; ++i) sam.insert(str[i] - ‘a‘);   
}
 
void solve() {
  for (int i = 1; i <= N; ++i) {
    scanf("%s", str2);
    L = strlen(str2);
    puts(sam.check(0, 0) ? "Yes" : "No");
  }
}
 
int main() {
  init();
  solve();
}