MnZn求助AC自动机
  • 板块灌水区
  • 楼主likezrh
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/7/7 12:09
  • 上次更新2023/10/27 21:38:06
查看原帖
MnZn求助AC自动机
737715
likezrh楼主2022/7/7 12:09

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

2022/7/7 12:09
加载中...