发现一个奇怪的问题
下面的这份代码,在洛谷提供的 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;