【序列自动机】Subsequence

题目地址：https://nanti.jisuanke.com/t/38232

求串A是否为串B的非连续子序列。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 30;
int n, len, rt;
char S[maxn], T[maxn];
int par[maxn];
int head[26], last[26];
int ch[maxn][26];
void insert_word(int x)//序列自动机模板
{
  par[++rt] = last[x];
  if (!last[x])
    head[x] = rt;
  for (int i = 0; i < 26; i++)
    for (int j = last[i]; j && ch[j][x] == 0; j = par[j])
    { 
      ch[j][x] = rt;
    }
      
  last[x] = rt;
}
bool find(char S[])
{
  int rt, len = strlen(S);
  for (int i = 0; i < len; ++i)
  {
    int x = S[i] - 'a';
    if (i == 0)
      rt = head[x];
    else rt = ch[rt][x];
    if (rt == 0)
      return 0;
  }
  return 1;
}
int main()
{
  scanf("%s", &S);
  len = strlen(S);
  for (int i = 0; i < len; ++i)
  {
    insert_word(S[i] - 'a');
  }
  cin >> n;
  for (int i = 0; i < n; ++i)
  {
    scanf("%s", &T);
    if (find(T))
      cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  return 0;
}

序列自动机可以O（n）判断一个串是否是另一个串的子串。大致思想是对于一个串的每个互不相同的子串，在其某一位置的字符只需要取最靠前的拿一个，比如aaabab,那么子串ab中的a只需要由原串第一个a产生，b由第一个b产生即可。建立一个类似trie的结构，对原串每一个字符，添加到trie中时只添加在每种字符的最后一个的后面。判断时顺着跑一遍就好了。

void insert_word(int x)
{
  par[++rt] = last[x];
  if (!last[x])
    head[x] = rt;
  for (int i = 0; i < 26; i++)
    for (int j = last[i]; j && ch[j][x] == 0; j = par[j])
    { 
      ch[j][x] = rt;
    }
      
  last[x] = rt;
}

似乎是个很冷门的东西呢