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

洛谷P5826 【模板】子序列自动机

题目链接：P5826 【模板】子序列自动机

题意：给定一个主序列，每次给出一个序列，判断是否为其子序列

我们可以把每个字符的出现位置用vector维护

然后对于每个询问，直接二分离当前位置最近的那个位置

使其变为当前位置，如果不存在则输出No

为什么选择最近的位置？贪心可知，选择尽可能近的位置可以产生更多的子序列

这个算法也叫子序列自动机

时间复杂度 O ( ∣ S ∣ + ∑ ∣ s i ∣ log ⁡ ∣ S ∣ ) O(|S| + \sum|s_i|\log|S|) O(∣S∣+∑∣si​∣log∣S∣)

代码如下（稍微卡了卡常）

#include 
using namespace std;
#define int long long
#define SIZ (int)(1e5+15)
#define gc() readchar()
#define pc(a) putchar(a)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    static T stk[66];T top=0;
    do{stk[top++]=k%10,k/=10;}while(k);
    while(top){pc(stk[--top]+'0');}
}
#define N (int)(1e5+15)
vector<int>pos[N];
int n,Q,_,m,a[N],b[N],lstpos,ok;
signed main()
{
    read(_);read(n);read(Q);read(_);
    for(int i=1; i<=n; i++)
    {
        read(a[i]);
        pos[a[i]].push_back(i);
    }
    while(Q--)
    {
        read(m);ok=1;lstpos=0;
        for(int i=1; i<=m; i++)
            read(b[i]);
        for(int i=1; i<=m; i++)
        {
            auto p=upper_bound(pos[b[i]].begin(),
            pos[b[i]].end(),lstpos);
            if(p==pos[b[i]].end()){ok=0;break;}
            lstpos=*p;
        }
        puts(ok?"Yes":"No");
    }
    return 0;
}

转载请说明出处