golang刷leetcode 经典（10） tire树与ac自动机

按下述要求实现 StreamChecker 类：

StreamChecker(words)：构造函数，用给定的字词初始化数据结构。

query(letter)：如果存在某些 k >= 1，可以用查询的最后 k个字符（按从旧到新顺序，包括刚刚查询的字母）拼写出给定字词表中的某一字词时，返回 true。否则，返回 false。

示例：


StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // 初始化字典
streamChecker.query('a');          // 返回 false
streamChecker.query('b');          // 返回 false
streamChecker.query('c');          // 返回 false
streamChecker.query('d');          // 返回 true，因为 'cd' 在字词表中
streamChecker.query('e');          // 返回 false
streamChecker.query('f');          // 返回 true，因为 'f' 在字词表中
streamChecker.query('g');          // 返回 false
streamChecker.query('h');          // 返回 false
streamChecker.query('i');          // 返回 false
streamChecker.query('j');          // 返回 false
streamChecker.query('k');          // 返回 false
streamChecker.query('l');          // 返回 true，因为 'kl' 在字词表中。

复制

提示：

1 <= words.length <= 2000

1 <= words[i].length <= 2000

字词只包含小写英文字母。

待查项只包含小写英文字母。

待查项最多 40000 个。

解题思路：

1，看到题目很多人想到的是ac自动机，但是ac自动机并不能解决这个问题

2，kmp 用来查找目标串在模式串中的位置

3，ac 自动机与之对应，用来查找目标串中是否包含，模式串。两者有很多相似性，比如kmp的next数组和ac自动机的fail指针类似，只不过，前者用来匹配相同前缀，后者用来匹配相同后缀（从root出发）

4，对于非root出发的后缀匹配，ac自动机解决不了，需要用tire 后缀树，与tire相似，只是建树和匹配的时候从字符串右边开始。

5，为了对比，先实现了一版标准的ac自动机

type StreamChecker struct {
    children [26]*StreamChecker
    fail *StreamChecker
    sum int
    val byte
    stream []byte
}

func (this*StreamChecker)Insert(word string){
    if word==""{
        return
    }
    cur:=this
    for i:=0;i<len(word);i++{
        if cur.children[word[len(word)-1-i]-'a']==nil{
            cur.children[word[len(word)-1-i]-'a']=&StreamChecker{
                val:word[len(word)-1-i],
            }
        }
        if i== len(word)-1{
            cur.children[word[len(word)-1-i]-'a'].sum++
        }
        cur=cur.children[word[len(word)-1-i]-'a']
    }
    return
}

func (this*StreamChecker)BuildFailPointer(){    
    if this==nil{
        return
    }

    var q Queue
    q.Push(this)

    for !q.Empty(){ //广度优先搜索
        cur:= q.Pop()
        for i:=0;i<26;i++{
            if cur.children[i]!=nil{
                if cur==this{
                    //cur.fail=this   不能有，否则for fail!=nil {｝ 死循环了
                    cur.children[i].fail=this
                }else{
                    fail:=cur.fail
                    for fail!=nil {
                        if fail.children[i]!=nil{
                           cur.children[i].fail = fail.children[i]
                            break
                        }
                        fail=fail.fail
                    }
                    if fail==nil{
                        cur.children[i].fail=this
                    }
                }
                 q.Push(cur.children[i])
            }
        }
    }
    return 
}

func (this*StreamChecker)Print(root*StreamChecker){
    cur:=this
    if cur==nil{
        return
    }
    fmt.Print("\nval:",string([]byte{cur.val}),"->children:")
    for i:=0;i<26;i++{
        if cur.children[i]!=nil{
            fmt.Print(string([]byte{byte(i)+'a'}))
        }
    }
    fmt.Println("->",cur.sum,cur.fail==root,cur.fail==nil)
    if cur.fail!=nil{
        fmt.Println("fail:",string([]byte{cur.fail.val}))
    }else{
        fmt.Println("fail:",cur.fail)
    }
    for i:=0;i<26;i++{
        cur.children[i].Print(root)
    }
    return
}
func Constructor(words []string) StreamChecker {
    var sc StreamChecker
    for _,w:=range words{
         sc.Insert(w)
    }
    sc.BuildFailPointer()
    sc.Print(&sc)
    return sc
}


func (this *StreamChecker) Query(letter byte) bool {
    this.stream=append(this.stream,letter)
    letters:=string(this.stream)
    if letters==""{
        return false
    }
    cur:=this
    sum:=0
    for i:=0;i<len(letters);i++{
        if cur.children[letters[i]-'a']!=nil{
            cur=cur.children[letters[i]-'a']
            sum+=cur.sum
        }else{
            fail:=cur.fail
            for fail!=nil && fail.children[letters[i]-'a']==nil{
                fail=fail.fail
            }
            if fail==nil {
                cur=this
            }else{
                cur=fail.children[letters[i]-'a']
                sum+=cur.sum
            }
        }
    }
    return sum>0
}

type Queue struct{
    data []*StreamChecker
}
func (this* Queue)Push(node *StreamChecker){
  this.data=append(this.data,node)
}

func (this*Queue)Pop()*StreamChecker{
   if this.Empty(){
       return nil
   }
   node:=this.data[0]
   this.data=this.data[1:]
   return node
}

func (this*Queue)Empty()bool{
    return len(this.data)==0
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * obj := Constructor(words);
 * param_1 := obj.Query(letter);
 */

复制

6，这是真正的解题代码

type StreamChecker struct {
    children [26]*StreamChecker
    sum int
    val byte
    stream []byte
}

func (this*StreamChecker)Insert(word string){
    if word==""{
        return
    }
    cur:=this
    for i:=0;i<len(word);i++{
        if cur.children[word[len(word)-1-i]-'a']==nil{
            cur.children[word[len(word)-1-i]-'a']=&StreamChecker{
                val:word[len(word)-1-i],
            }
        }
        if i== len(word)-1{
            cur.children[word[len(word)-1-i]-'a'].sum++
        }
        cur=cur.children[word[len(word)-1-i]-'a']
    }
    return
}

func Constructor(words []string) StreamChecker {
    var sc StreamChecker
    for _,w:=range words{
         sc.Insert(w)
    }
    return sc
}


func (this *StreamChecker) Query(letter byte) bool {
    this.stream=append(this.stream,letter)
    cur:=this
    for i:=0;i<len(this.stream);i++{
        if cur.children[this.stream[len(this.stream)-1-i]-'a']==nil{
            return false
        }else{
            cur= cur.children[this.stream[len(this.stream)-1-i]-'a']
            if cur.sum>0{
                return true
            }
        }
    }
    return false
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * obj := Constructor(words);
 * param_1 := obj.Query(letter);
 */

复制