社区讨论
自动机写法WA+TLE,玄关求助dalao,有详细注释
P5826【模板】子序列自动机参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mhjkyj3y
- 此快照首次捕获于
- 2025/11/04 04:16 4 个月前
- 此快照最后确认于
- 2025/11/04 04:16 4 个月前
Q1:样例全NO,不知道哪里出错
Q2:蒟蒻不会可持久化,如何优化TLE
CPP#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int type,n,q,m,a[N],b[N];
vector<vector<int> > build_dfa(int *s,int l){ //建立一个自动机,const string 常量字符串
int n=l;
vector<vector<int> > ne(n+1,vector<int>((int)1e6,-1));//
//1. (n + 1, ...)
// 初始化外层向量的大小为 n + 1,其中 n 是主串的长度。外层向量的每个元素代表主串中的一个位置(索引范围:0 到 n)。
//2. vector<int>(26, -1)
// 定义内层向量的初始化方式:
//3. 26:每个内层向量的大小为 26,对应小写字母 'a' 到 'z'。
//4. -1:所有元素初始值为 -1,表示 “未找到” 或 “不存在”。
for(int i=n-1;i>=0;i--){//从预处理时,代码从主串的最后一个字符向前遍历,确保每个位置 i 的转移信息包含后续所有字符的最早出现位置。
for(int c=0;c<(int)1e6;c++){
ne[i][c]=ne[i+1][c];
// c=s[i]-'a';//字符转整数
ne[i][c]=i;//在转移表 next 中记录:从位置 i 开始,字符 c(即 s[i])首次出现的位置是 i 本身。
//对于同一字符 c,后处理的位置(较小的 i)会覆盖先处理的位置(较大的 i),从而保证 next[i][c] 存储的是最早出现位置。
}
}
return ne;
}
string quary(int len,vector<vector<int> > ne,int *s){
int now=0;// 记录当前位置
for(int i=1;i<=len;i++){//是一种基于范围的 for 循环,用于遍历容器或序列中的每个元素。具体来说,它会依次将字符串 s 中的每个字符赋值给变量 c。
if(ne[now][s[i]]==-1){ //表示在这之后C不再出现
return "No";
}
now=ne[now][s[i]]+1;//更新节点到当前节点指向的C 的那个节点的下一个节点标号,似乎有点像遍历链表
}
return "Yes";
}
int main(){
ios::sync_with_stdio(false);
cout.tie(0),cin.tie(0);
cin>>n>>q>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int l,a[N];
vector<vector<int> > xxx=build_dfa(a,l);
while(q--){
cin>>l;
for(int i=1;i<=l;i++) cin>>b[i];
cout<<quary(l,xxx,b)<<'\n';
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...