算法 - AC自动机 - 《Leetcode》

构建步骤
- fail
演示
参考

构建步骤

AC自动机的构造分成两步：

构造Trie树
在Trie树的基础上构建fail指针（相当于KMP的next数组）
fail
构造失败指针的过程概括起来就一句话：设这个节点上的字母为C，沿着它父亲节点的失败指针走，直到走到一个节点，它的子结点中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了root都没找到，那就把失败指针指向root。
具体操作起来只需要：先把root加入队列(root的失败指针指向自己或者NULL)，这以后我们每处理一个点，就把它的所有儿子加入队列。

观察构造失败指针的流程：对照图来看。
(1) 首先root的fail指针指向NULL，然后root入队，进入循环。
(2) 从队列中弹出root，root节点与h、s节点相连，因为它们是第一层的字符，肯定没有比它层数更小的共同前后缀，所以把这2个节点的失败指针指向root，并且先后进入队列，失败指针的指向对应图中的(1)，(2)两条红线；
(3) 从队列中先弹出h(左边那个)，h所连的只有e结点，所以接下来扫描指针指向e节点的父节点h节点的fail指针指向的节点，也就是root，root->next[‘e’] == NULL,并且root->fail == NULL,说明匹配序列为空，则把节点e的fail指针指向root,对应图中的蓝色，然后节点e进入队列；
(4)从队列中弹出s，s节点与a,h(左边那个)相连，先遍历到a节点，扫描指针指向a节点的父节点s节点的fail指针指向的节点，也就是root，root->next[‘a’] == NULL,并且root->fail == NULL,说明匹配序列为空,则把节点a的fail指针指向root,对应图中的蓝色,然后节点a进入队列。
(5)接着遍历到h节点，扫描指针指向h节点的父节点s节点的fail指针指向的节点，也就是root，root->next[‘h’] != NULL,所以把节点h的fail指针指向右边那个h,对应图中的蓝色,然后节点h进入队列…由此类推，最终失配指针如图所示。

演示

Go创建AC

package goAcAutoMachine
type AcNode struct {
    fail      *AcNode
    isPattern bool
    next      map[rune]*AcNode
}
func newAcNode() *AcNode {
    return &AcNode{
        fail:      nil,
        isPattern: false,
        next:      map[rune]*AcNode{},
    }
}
type AcAutoMachine struct {
    root *AcNode
}
func NewAcAutoMachine() *AcAutoMachine {
    return &AcAutoMachine{
        root: newAcNode(),
    }
}
func (ac *AcAutoMachine) AddPattern(pattern string) {
    chars := []rune(pattern)
    iter := ac.root
    for _, c := range chars {
        if _, ok := iter.next[c]; !ok {
            iter.next[c] = newAcNode()
        }
        iter = iter.next[c]
    }
    iter.isPattern = true
}
func (ac *AcAutoMachine) Build() {
    queue := []*AcNode{}
    queue = append(queue, ac.root)
    for len(queue) != 0 {
        parent := queue[0]
        queue = queue[1:]
        for char, child := range parent.next {
            if parent == ac.root {
                child.fail = ac.root
            } else {
                failAcNode := parent.fail
                for failAcNode != nil {
                    if _, ok := failAcNode.next[char]; ok {
                        child.fail = parent.fail.next[char]
                        break
                    }
                    failAcNode = failAcNode.fail
                }
                if failAcNode == nil {
                    child.fail = ac.root
                }
            }
            queue = append(queue, child)
        }
    }
}
func (ac *AcAutoMachine) Query(content string) (results []string) {
    chars := []rune(content)
    iter := ac.root
    var start, end int
    for i, c := range chars {
        _, ok := iter.next[c]
        for !ok && iter != ac.root {
            iter = iter.fail
        }
        if _, ok = iter.next[c]; ok {
            if iter == ac.root { // this is the first match, record the start position
                start = i
            }
            iter = iter.next[c]
            if iter.isPattern {
                end = i // this is the end match, record one result
                results = append(results, string([]rune(content)[start:end+1]))
            }
        }
    }
    return
}

参考

http://keyblog.cn/article-39.html