社区讨论

有关AC自动机(简单版)的几点疑问

P3808AC 自动机(简单版)参与者 3已保存回复 4

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@lochd249
此快照首次捕获于
2023/10/30 13:49
2 年前
此快照最后确认于
2023/11/05 01:17
2 年前
查看原帖
关于fail数组的求解
CPP
void getFail(){
    queue <int>q;
    for(int i=0;i<26;i++){      
        if(trie[0][i]){
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
} 
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i=0;i<26;i++){      
            if(trie[now][i]){
                fail[trie[now][i]] = trie[fail[now]][i];
                q.push(trie[now][i]);
            }
            else//让当前节点的这个子节点
                //指向当前节点fail指针的这个子节点
                trie[now][i] = trie[fail[now]][i];
        }
    }
}
为什么在trie[now][i]不存在的情况下,也就是now号结点的编号为i的孩子不存在,就让trie[now][i]指向他的fail结点的i号结点,而不是直接指向root?他实际不是不存在的吗,为什么还要指向?
CPP
int query(string s){
    int now = 0,ans = 0;
    for(int i=0;i<s.size();i++){    
        now = trie[now][s[i]-'a'];  //从s[i]点开始寻找
        for(int j=now;j && cntword[j]!=-1;j=fail[j]){
            //一直向下寻找,直到匹配失败(失败指针指向根或者当前节点已找过).
            ans += cntword[j];
            cntword[j] = -1;    //标记,防止重复计算 
        }
    }
    return ans;
}
关于query函数:这里for里面说的是一直向下寻找,但是找到的却是他的fail结点,也就是一直在向root方向寻找,那不应该是向上寻找吗?寻找的过程难道不应该是找不到下一个字母再跳到fail指针上吗,怎么他一直跳到fail指针上,不管找没找到?

回复

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

正在加载回复...