社区讨论

自动机写法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 条回复,欢迎继续交流。

正在加载回复...