子序列自动机

子序列自动机

传送门

题目要我们求，给定一个序列是否是原串的子序列，那么我们就要快速找到下一位的在原串中的匹配位置。

为了能让子串尽可能匹配，所以我们要找到的匹配位置尽量靠前，而且我们发现，我们是按位匹配的，所以可以用可持久化线段树（主席树）来处理。

我们要找的是最近的点，所以将串从后往前处理，这样就可以将更近的点不断更新，最后剩下的就是最优的解（这个字符后每个字符最近的位置）。

主席树代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<queue>
using namespace std;
int r_r(){//快读 
  int x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
const int o_o=2e6+10;
int op,n,q,m;
int a_a[o_o],b_b[o_o];
struct po{
  int l_s;//左子树 
  int r_s;//右子树 
  int i;//编号 
}t_r[o_o];
int x_p=0;
void u_p(int v,int x,int &n_w,int k_k,int l=1,int r=m){
  if(v<l||r<v){//超出范围 
    n_w=k_k;//直接复制根节点信息 
    return;
  }
  n_w=++x_p;//建新点 
  t_r[n_w].l_s=0;
  t_r[n_w].r_s=0;
  t_r[n_w].i=0;
  //初始化新节点 
  
  if(l==r){//找到范围 
    t_r[n_w].i=x;//存坐标 
    return;
  }
  int m_i=(l+r)>>1;
  if(m_i>=v)u_p(v,x,t_r[n_w].l_s,t_r[k_k].l_s,l,m_i);//左子树 
  else t_r[n_w].l_s=t_r[k_k].l_s;
  if(m_i+1<=v)u_p(v,x,t_r[n_w].r_s,t_r[k_k].r_s,m_i+1,r);//右子树 
  else t_r[n_w].r_s=t_r[k_k].r_s;
}
int f_i(int x,int k_k,int l=1,int r=m){
  if(x<l||r<x)return 0;//超出目标范围 
  if(l==r)return t_r[k_k].i;//找到目标叶子结点 
  int m_i=(l+r)>>1; 
  return f_i(x,t_r[k_k].l_s,l,m_i)+f_i(x,t_r[k_k].r_s,m_i+1,r);//统计结果 
}
int g_g[o_o];//每个节点作为根的编号存储 
int main(){
    op=r_r(),n=r_r(),q=r_r(),m=r_r();
  for(int i=1;i<=n;i++)a_a[i]=r_r();//读入序列 
  for(int i=n;i>=1;i--)u_p(a_a[i],i,g_g[i],g_g[i+1]);//将每个点放入树中 
  for(int i=1;i<=q;i++){//多组询问 
    int x_k=r_r();//读取匹配序列长度 
    x_p=0;
    int k_k=1;//开始位置 
    bool b_p=0;//标记是否失败 
    for(int i=1;i<=x_k;i++)b_b[i]=r_r();//读取匹配序列 
    for(int i=1;i<=x_k;i++){
      k_k=f_i(b_b[i],g_g[k_k]);//匹配位置 
      if(k_k==0){//找不到了 
        b_p=1;//标记 
        break;
      }
      k_k++;//进入下一个，当前值已经用过了 
    }
    if(b_p)puts("No");
    else puts("Yes");
  }
  return 0;
}

但是我们还可以用 STL 来做，通过 vector 将每个字符的坐标存下来，在子串匹配的时候，需要什么字符可以直接访问，同时我们存坐标时是有序的（升序），所以可以二分来更快的访问最近的合法位置匹配。

二分代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<queue>
using namespace std;
int r_r(){//快读 
  int x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
const int o_o=2e6+10;
vector<int> p_p[o_o];
int main(){
  int t_p=r_r(),n=r_r(),q=r_r(),m=r_r();//读入基本信息 
  for(int i=1;i<=n;i++)p_p[r_r()].push_back(i);//将每从个数的值直接放入到 
  while(q--){
    int l=r_r(),x_x=0;//记录开始的位置，初始化初值 
    bool b_b=1;//初始化判断的 
    while(l--){
      int x=r_r();//读入当前值 
      if(!b_b)continue;//已经不符合要求直接退出循环 
      vector<int>::iterator k_k=lower_bound(p_p[x].begin(),p_p[x].end(),x_x+1);//二分最接近的值 
      if(k_k==p_p[x].end())b_b=0;//变化判断的值 
      else x_x=*k_k;//累计结果 
    }
    if(b_b)puts("Yes");//符合要求 
    else puts("No");//不符合要求 
  }
}