AC自动机

ac自动机

1.根据字符构造trie树
2.构建失败匹配指针
   1.根节点的所以一代子孩子失败指针都指向root
   2.子节点匹配失败时，找到父节点的失败指针，找不到就一直找，直到找到root还匹配不到，直接指向root
3.文本串匹配
   1.如果已经匹配到完整的模式串或者压根匹配不到，根据失败指针切换线路继续向下查找
   2.如果匹配到了，那么就继续向下匹配

class acnode {
    constructor(data){
        this.data = data
        this.isendingchar = false
        this.children = new map()
        this.length = 0
        this.fail = null
    }
}

class actree {
    constructor(){
        this.root = new acnode('/')
    }
    insert(text){
        let node = this.root
        for(let char of text ){
            if(!node.children.get(char)){
                node.children.set(char,new acnode(char))
            }
            node = node.children.get(char)
        }
        node.isendingchar = true
        node.length = text.length
    }
    failurepointer(){
        let root = this.root
        let queue = []
        queue.push(root)
        while(queue.length > 0){
            let currentnode = queue.shift()
            for(let child of currentnode.children.values()){
                if(!child){
                    continue
                }

                if(currentnode == root){
                    child.fail = currentnode
                }else{
                    //不是一代子节点才指向
                    let grandfathernode = currentnode.fail
                    while(grandfathernode){
                        let failnode = grandfathernode.children.get(child.data)
                        if(failnode){
                            child.fail = failnode
                            //找到失败节点就不往下找了
                            break
                        }
                        grandfathernode = grandfathernode.fail
                    }
                    if(!grandfathernode){
                        child.fail = root
                    }
                }               
                queue.push(child)
            }
        }
    }
    match(text){
        let root = this.root
        let len =  text.length
        let currentnode
        for(let i = 0; i < len; i++){
            let char = text[i]

            if(!currentnode){
                currentnode = root
            }

            while(!currentnode.children.get(char) && currentnode != root){
                //匹配不到就换线
                currentnode = currentnode.fail
            }

            currentnode = currentnode.children.get(char)

            let tmp = currentnode
            while(tmp != root){
                if(tmp.isendingchar){
                    console.log(`from ${i - tmp.length + 1} length: ${tmp.length} str: ${text.substr(i - tmp.length + 1,tmp.length)}`)
                }
                //匹配到了就继续看看其他线有没有可以匹配成功的
                tmp = tmp.fail 
            }

        }
    }
}

function match(text,patterns){
    const autometa = new actree()
    for(pattern of patterns){
        autometa.insert(pattern)
    }
    autometa.failurepointer()
    autometa.match(text)
}

let patterns = ["at", "art", "oars", "soar"];
let text = "soarsoars";
match(text, patterns);

let patterns2 = ["fxtec pro1", "谷歌pixel"];
let text2 = "一家总部位于伦敦的公司fxtex在mwc上就推出了一款名为fxtec pro1的手机，该机最大的亮点就是采用了侧滑式全键盘设计。dxomark年度总榜发布 华为p20 pro/谷歌pixel 3争冠";
match(text2, patterns2);