RT,AC 自动机上的状态转移为什么只能从fail节点转移到当前节点,而不能从当前节点转移到fail节点。
比如P2444中构建fail指针的代码
inline void build()
{
queue<int> q;
for (int i = 0; i < 2; i++)
if (t[0][i])
q.push(t[0][i]);
while (q.size())
{
int p = q.front();
q.pop();
for (int i = 0; i < 2; i++)
{
int c = t[p][i];
if (!c) t[p][i] = t[fail[p]][i];
else
{
fail[c] = t[fail[p]][i];
safe[c] |= safe[fail[c]];
q.push(c);
}
}
}
}
改为
inline void build()
{
queue<int> q;
for (int i = 0; i < 2; i++)
if (t[0][i])
q.push(t[0][i]);
while (q.size())
{
int p = q.front();
q.pop();
for (int i = 0; i < 2; i++)
{
int c = t[p][i];
if (!c) t[p][i] = t[fail[p]][i];
else
{
fail[c] = t[fail[p]][i];
safe[c] |= safe[fail[c]];
safe[fail[c]] |= safe[c];
q.push(c);
}
}
}
}
就会WA