【模板】子序列自动机
2022/7/24 23:25:59
本文主要是介绍【模板】子序列自动机,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
link
其实感觉这玩意不应该叫什么自动机,这似乎就是一个个人yy出来的东西。。。
给定一个文本串和许多模式串,询问每个模式串是不是文本串的子序列。如果是询问字串的话直接上kmp即可,但子序列呢。考虑贪心,寻找文本中第一个和模式串第一个元素相同的元素位置,选择它相较于选择其它值相同的元素肯定不劣,毕竟它相当于是给后面的元素留出更多的选择余地。于是问题就变成了依次寻找,每次在某个元素的位置集合中寻找第一个在某个位置后面的第一个位置即可,于是想到用vector存每个元素的位置集合然后直接二分,写起来很简单。
#include<bits/stdc++.h> //#define feyn const int N=100010; using namespace std; inline void read(int &wh){ wh=0;int f=1;char w=getchar(); while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();} while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();} wh*=f;return; } int m,n,len,in; vector<int>a[N]; signed main(){ #ifdef feyn freopen("in.txt","r",stdin); #endif read(m);read(m);read(n);read(in); for(int i=1;i<=m;i++){ read(in);a[in].push_back(i); } while(n--){ read(len);int now=0;bool ok=true; for(int i=1;i<=len;i++){ read(in); vector<int>::iterator it=upper_bound(a[in].begin(),a[in].end(),now); if(it==a[in].end())ok=false; else now=*it; } if(ok)printf("Yes\n"); else printf("No\n"); } return 0; }
这篇关于【模板】子序列自动机的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?