温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

序列自动机

发布时间:2020-08-13 14:54:12 来源:网络 阅读:615 作者:qinXpeng 栏目:编程语言
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 1000000 + 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);
  }
} T;
void init() {
  scanf("%s", str);
  scanf("%d", &N);
  for (int i = 0; str[i]; ++i) T.insert(str[i] - 'a');
}
void solve() {
  for (int i = 1; i <= N; ++i) {
    scanf("%s", str2);
    L = strlen(str2);
    puts(T.check(0, 0) ? "Yes" : "No");
  }
}
int main() {
  init();
  solve();
  return 0;
}
向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI