一个网站主页开发费用,陈村九江网站建设,网站开发的主要步骤,wordpress 转nodejs所谓子序列自动机#xff0c;就是根据子序列建立的自动机。 #xff08;逃#xff09;
前言
小清新算法。
解析
和其他自动机类似的#xff0c;我们希望子序列自动机能且只能接受原串的所有子序列。
考虑一个问题#xff1a;给你一个串 T#xff0c;如何判断它是否是… 所谓子序列自动机就是根据子序列建立的自动机。 逃
前言
小清新算法。
解析
和其他自动机类似的我们希望子序列自动机能且只能接受原串的所有子序列。
考虑一个问题给你一个串 T如何判断它是否是原串 S 的子串 一个经典的贪心策略是设当前在 T 的匹配位置是 iS 的匹配位置是 j那么就找到 S 的位置 j 之后第一个 T[i1] 出现的位置 p然后令 ii1,jp直到T全部匹配或S失配为止。
把类似的思想迁移到子序列自动机上设 toi,jto_{i,j}toi,j 表示 i 之后 第一个 j 出现的位置匹配的时候不断跳 to 就行了to数组可以通过倒着扫一边求解。
字符集较小时直接暴力为 to 数组赋值即可字符集较大的时候考虑到 toito_itoi 和 toi1to_{i1}toi1 只有一位不同所以使用可持久化线段树即可复杂度可能要多一个 log。
代码
P5826 【模板】子序列自动机
#includebits/stdc.h
using namespace std;
#define ll long long
#define ULL unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-) f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N1e5100;
const int mod998244353;
const ll inf1e9;bool mem1;bool Flag0;int n,m,q;struct node{int ls,rs,w;
}tr[N*20];
int rt[N],tot;
inline int copy(int x){tr[tot]tr[x];return tot;
}
#define mid ((lr)1)
void upd(int k,int l,int r,int p,int w){kcopy(k);if(lr){tr[k].ww;return;}if(pmid) upd(tr[k].ls,l,mid,p,w);else upd(tr[k].rs,mid1,r,p,w);//printf( k%d (%d %d) ls%d rs%d\n,k,l,r,tr[k].ls,tr[k].rs);
}
int ask(int k,int l,int r,int p){//printf( k%d (%d %d) ls%d rs%d\n,k,l,r,tr[k].ls,tr[k].rs);if(!k) return n1;if(lr) return tr[k].w;if(pmid) return ask(tr[k].ls,l,mid,p);else return ask(tr[k].rs,mid1,r,p);
}
int a[N];int main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifread();nread();qread();mread();tr[0].wn1;for(int i1;in;i) a[i]read();for(int in-1;i0;i--){//printf(i%d\n,i);rt[i]rt[i1];upd(rt[i],1,m,a[i1],i1);}for(int t1;tq;t){int lenread();for(int i1;ilen;i) a[i]read();int p0;for(int i1;ilenpn;i){pask(rt[p],1,m,a[i]);//printf( i%d a%d p%d\n,i,a[i],p);}if(pn) puts(Yes);else puts(No);}return 0;
}
/*
*/
