洛谷 5826 【模板】子序列自动机 题解

发表于 | 更新于 | 阅读次数：
本文字数： 1.5k 字 | 阅读时长 ≈ 6 分钟

你以为我只是单纯的子序列自动机吗？其实我是是子序列自动机+可持久化数组哒！

但是我看见一个大神给出了一个特别神仙又巧妙的思路！我不禁要写一篇题解记录下这神奇的思路！

而且代码贼短哦~比可持久化数组好写到不知道多少倍呢www

题意简述

给定一个序列$A$长度<=1e5，还要一些要询问的字符串$B$，长度和$<=1e6$。对于每个$B$，询问其是否是$A$的子序列。序列中的每个值都在$1e5$以内。

思路框架

在暴力匹配子序列的时候，用链表（或者vector）记录哪些询问的答案会被更新即珂。复杂度$O(1e6+1e5)$。

具体思路

这个思路是洛谷上一个叫“丁文涛2004”的神仙写的一个“链式前向星-子序列自动机”。非常强大。借这篇文章膜一下这个巨佬。

正片开始。我们知道，朴素的子序列的查询是$O(|A|\times |B|)$的。我们大约是这样写的：

1
2
int p=1;
F(i,1,|A|) if (A[i]==B[p]) ++p;

然后判断是否p==|B|。其中$p$表示我们当前匹配到了哪一个位置。

子序列自动机：设$nxt[i][j]$表示$i$往后第一个值为$j$的出现在哪一个位置。这样的确方便查询，但是这里值域$1e5$，这个做法显然没救了。

考虑优化第一个方法：把所有的询问放到一块来处理。那么，当我们找到一个A[i]的时候，所有满足B[p]==A[i]的p都会执行p++操作。

那么我们只要记录所有B[p]==A[i]的B[p]都在哪些位置就好了。所以，首先要用一个链表（链式前向星），把$B$的值按输入顺序串起来。然后要用一个链表把$B$按值域分类。具体的，记$head[i]$表示$B$中值为$i$的数最后一个出现的位置，$nxt[i]$表示$B$中前一个和$B[i]$相同的。然后我们令$cur=head[xxx]$，不断的令$cur=nxt[cur]$，就珂以找到$B$中所有值为$xxx$的位置了。

然后，我们在把$B$按输入顺序穿起来的时候，对于每个$B$的最后一个字符，我们令它的下一个值为$-i$，其中$i$为这个$B$在输入中的编号。这样，

“既判定了匹配到了末尾，又判定了当前所在的字符串（的编号，博主注），可谓一举两得~”（作者原话）

关于如何处理询问：
我们以$A$为基准，不断在$B$中找到匹配。对于每个$A[i]$，我们通过遍历前向星找到$B$中值为$A[i]$的位置。如果这个位置是最后一个位置，那么这个$B$就匹配成功，我们标记它是$A$的子序列。否则，我们把原来的指针指向$B[i]$的删掉，连接上$B[i+1]$，就是实现上面的$p++$操作。

然后我们发现，如果匹配成功了，也要删掉指针。那就不如在遍历到$A[i]$的时候，直接全部清空好了。（链式前向星清空很简单，只要令$head[A[i]]=0$即珂。）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 1666666
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    int type,n,q,m;//type:没什么用，给你骗分用的。满分的代码是不需要骗分的。
    int a[N];
    void Input()
    {
        R1(type);R1(n),R1(q),R1(m);
        F(i,1,n) R1(a[i]);
    }

    int len[N],nxtb[N],valb[N],cntb; //按输入顺序记录B的链表们www
    //len[i]:  第i个询问中B的长度
    //nxtb[i]: 用来把B串起来。记录下标。一般nxt[i]=i+1。如果i到末尾了，那么nxtb[i]=-id。
    //id为这个B的编号。这一步的妙处上面说了
    //valb[i]: 和nxtb区别，这个是记录B的值。
    //cntb:    总共有多少个点。到最后，它的值就等于len[i]的和。  
    int node[N],head[N],nxt[N],cntval; //按B的值域分类记录的链表们www
    //node[i]: 记录点在B中的编号,方便求出nxtb
    //head[i]: 记录B中最后一个值为i的位置(这边的位置是在链表中的位置，而不是B中的位置)。
    //nxt[i]:  记录B中下一个和i的值相同的位置。
    bool cxk[N];
    //cxk[i]:  第i个询问是否是子序列
    void Add(int u,int v) //B中值为u的位置添加上一个v
    {
        node[++cntval]=v;nxt[cntval]=head[u];head[u]=cntval;
    }
    void Soviet()
    {
        #define YES (putchar('Y'),putchar('e'),putchar('s'),putchar('\n'))
        #define NO  (putchar('N'),putchar('o'),putchar('\n'))
        //卡常数,putchar快，比puts快一些呢

        cntval=cntb=0; //初始化(没什么用)
        F(i,1,q)
        {
            R1(len[i]);
            R1(valb[++cntb]);Add(valb[cntb],cntb); //把B串起来，顺便记录值域
            F(j,2,len[i])
            {
                nxtb[cntb]=cntb+1;R1(valb[++cntb]); //串起来B
            } 
            nxtb[cntb]=-i; //好东西，上面讲了
        }
        F(i,1,n)
        {
            int cur=head[a[i]];head[a[i]]=0; //删他娘的
            for(;cur!=0;cur=nxt[cur])
            {
                int u=node[cur],v=nxtb[u];
                if (v<0) cxk[-v]=1; //v<0，说明到了末尾
                else Add(valb[v],v); //否则就新加上
            }
        }
        F(i,1,q)
        {
            if (cxk[i]) YES;
            else NO;
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w