社区讨论

求助关于basic_string扩容的疑似UB

学术版参与者 11已保存回复 22

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
20 条
当前快照
1 份
快照标识符
@mjqhi9zm
此快照首次捕获于
2025/12/29 09:33
2 个月前
此快照最后确认于
2026/01/01 16:05
2 个月前
查看原帖
CPP
template<const signed N=26>struct PAM{
	int sz=0,now,p0,p1;
	basic_string<int>fail,nxt[N],dep,len,info;
	int create(){
		fail+=-1;
		for(int i=0;i<N;i++)nxt[i]+=-1;
		dep+=0;
		len+=-1;
		return sz++; 
	}
	PAM(){
		p0=create();
		p1=create();
		fail[p0]=p1;
		len[p0]=0;
		now=p1;
	}
	int append(int v){
		int p=now,pos=info.size();
		info+=v;
		while(pos-len[p]<1||info[pos-len[p]-1]!=v){
			p=fail[p];
		}
		if(~nxt[v][p]){
			now=nxt[v][p];
			return now;
		}
		
		now=create();
		nxt[v][p]=now;
//		nxt[v][p]=(now=create());
		
		len[now]=len[p]+2;
		if(p==p1){
			fail[now]=p0;
			dep[now]=1;
			return now;
		}
		p=fail[p];
		while(pos-len[p]<1||info[pos-len[p]-1]!=v)p=fail[p];
		fail[now]=nxt[v][p];
		dep[now]=dep[fail[now]]+1;
		return now;
	}
	void print(){
		printf("info:[");for(int x:info)printf("%d ",x);printf("]\n");
		for(int i=0;i<sz;i++){
			printf("Node %d: fail:%d dep:%d len:%d son:{",i,fail[i],dep[i],len[i]);
			for(int j=0;j<N;j++)if(~nxt[j][i])printf("[%d:%d]",j,nxt[j][i]);
			printf("}\n");
		}
	}
};
求问,如上 PAM 在高亮部分采用 now=create();nxt[v][p]=now; 能够正常运行,而采用 nxt[v][p]=(now=create()); 时在本地 Dev-c++ TDM-GCC 4.9.2 64-bit Release 编译指令 -std=c++14 就会内容出错,而在洛谷上能通过。两者理应无区别。
根据我进一步的研究,发现是在 create 函数中 nxt[v] 进行了扩容导致赋值没有实际赋值上去,望大佬解答。

回复

22 条回复,欢迎继续交流。

正在加载回复...