蒟蒻求问 AC 自动机
查看原帖
蒟蒻求问 AC 自动机
753993
daitouzero楼主2023/2/3 21:09

发现一个奇怪的问题

下面的这份代码,在洛谷提供的 GCC9 的编译环境下无法通过(莫名 RE),在其他 C++ 语言环境(GCC11)情况下可以正常运行,但是貌似感觉没有 UB 或者之类的东西,想问问各位大佬为什么。

目前可以确定是 AC 自动机出了锅,但奇怪的是在不封装成 struct 或者使用 STL 队列时都可正常工作。

核心代码:

struct TRIE
{
	int son[1000005][maxwordset],tot;
	int isEnd[1000005];
	int Hash[256],id;
	TRIE()
	{
		tot=id=0;
		memset(son,0,sizeof(son));
		memset(Hash,0,sizeof(Hash));
		memset(isEnd,0,sizeof(isEnd));
	}
	inline void init(bool issmallword,bool islargeword,bool isnum)
	{
		if (issmallword) for (char c='a';c<='z';c++) Hash[c]=id++;
		if (islargeword) for (char c='A';c<='Z';c++) Hash[c]=id++;
		if (isnum) for (char c='1';c<='9';c++) Hash[c]=id++;
	}
	inline void insert(char word[],int len)
	{
		int pos=0;
		for (int i=0;i<len;pos=son[pos][Hash[word[i++]]])
			if (!son[pos][Hash[word[i]]])
				son[pos][Hash[word[i]]]=++tot;
		isEnd[pos]++;
	}
	inline int query_cnt(char word[],int len)
	{
		int pos=0;
		for (int i=0;i<len;pos=son[pos][Hash[word[i++]]])
			if (!son[pos][Hash[word[i]]]) return 0;
		return isEnd[pos];
	}
	inline bool query_ishave(char word[],int len)
	{
		int pos=0;
		for (int i=0;i<len;pos=son[pos][Hash[word[i++]]])
			if (!son[pos][Hash[word[i]]]) return false;
		return true;
	}
};
struct AC_Automaton
{
	TRIE trie;
	int fail[1000005];
	bool vis[1000005];
	int qhead,tail,q[30000000];
	AC_Automaton()
	{	
		memset(q, 0, sizeof(q));
		memset(fail,0,sizeof(fail));
		memset(vis,false,sizeof(vis));
	}
	inline void init(bool issmallword,bool islargeword,bool isnum) {trie.init(issmallword,islargeword,isnum);}
	inline void insert(char word[],int len) {trie.insert(word,len);}
	inline void getfail()
	{
		//queue<int> q;
		//q.clear();
		q[0]=0;
		qhead=tail=0;
		for (int i=0;i<maxwordset;i++)
			if (trie.son[0][i]) 
			{
				fail[trie.son[0][i]]=0;
				q[++tail]=trie.son[0][i];
				//q.push(trie.son[0][i]);
			}
		int pos;
		//while (!q.empty())
		while (qhead<tail)
		{
			qhead++;
			pos=q[qhead];
			//pos=q.front();q.pop();
			for (int i=0,Next;i<maxwordset;i++)
			{
				Next=trie.son[pos][i];
				if (Next)
				{
					fail[Next]=trie.son[fail[pos]][i];
					//q.push(Next);
					q[++tail]=Next;
				}
				else trie.son[pos][i]=trie.son[fail[pos]][i];
			}
		}
	}
	inline int runit(char word[],int len)
	{
		int pos,ans=0;
		for (int i=0;i<len;i++)
		{
			pos=trie.son[pos][trie.Hash[word[i]]];
			for (int j=pos;j&&(!vis[j]);j=fail[j])
			{
				ans+=trie.isEnd[j];
				vis[j]=true;
			}
		}
		return ans;
	}
}AC;

完整代码如下

2023/2/3 21:09
加载中...