kmp tire树 ac自动机
kmp 用来查找目标串在模式串中的位置
ac 自动机与之对应，用来查找目标串中是否包含，模式串
两者有很多相似性，比如kmp的next数组和ac自动机的fail指针类似，只不过，前者用来匹配相同前缀，后者用来匹配相同后缀（从root出发，包含途径匹配）
对于非root出发的后缀匹配，ac自动机解决不了，需要用tire 后缀树，与tire相似，只是建树和匹配的时候从字符串右边开始。
ac 自动机的golang 实现
`
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 (thisStreamChecker)Print(rootStreamChecker){
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 (thisQueue)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);
/
`
后缀树
｀
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);
*/
｀
涉及到字符串的问题，无外乎这样一些算法和数据结构：自动机 KMP算法 Extend-KMP 后缀树 后缀数组 trie树 trie图及其应用。
extend-kmp 是kmp的扩展；ac自动机是kmp的多串形式；它是一个有限自动机；而trie图实际上是一个确定性有限自动机；ac自动机，trie图，后缀树实际上都是一种trie；后缀数组和后缀树都是与字符串的后缀集合有关的数据结构；trie图中的后缀指针和后缀树中的后缀链接这两个概念及其一致。
kmp
首先这个匹配算法，主要思想就是要充分利用上一次的匹配结果，找到匹配失败时，模式串可以向前移动的最大距离。这个最大距离，必须要保证不会错过可能的匹配位置，因此这个最大距离实际上就是模式串当前匹配位置的next数组值。也就是max{Aj 是 Pi 的后缀 j < i}，pi表示字符串A[1…i],Aj表示A[1…j]。模式串的next数组计算则是一个自匹配的过程。也是利用已有值next[1…i-1]计算next[i]的过程。我们可以看到，如果A[i] = A[next[i-1]+1] 那么next[i] = next[i-1]，否则，就可以将模式串继续前移了。
整个过程是这样的：
void next_comp(char * str){
int next[N+1];
int k = 0;
next[1] = 0;
//循环不变性，每次循环的开始，k = next[i-1]
for(int i = 2 ; i <= N ; i++){
//如果当前位置不匹配，或者还推进到字符串开始，则继续推进
while(A[k+1] != A[i] && k != 0){
k = next[k];
}
if(A[k+1] == A[i]) k++;
next[i] = k;
}
}
复杂度分析：从上面的过程可以看出，内部循环再不断的执行k = next[k]，而这个值必然是在缩小，也就是是没执行一次k至少减少1；另一方面k的初值是0，而最多++ N次，而k始终保持非负，很明显减少的不可能大于增加的那些，所以整个过程的复杂度是O(N)。
上面是next数组的计算过程，而整个kmp的匹配过程与此类似。
extend-kmp
为什么叫做扩展-kmp呢，首先我们看它计算的内容，它是要求出字符串B的后缀与字符串A的最长公共前缀。extend[i]表示B[i…B_len] 与A的最长公共前缀长度，也就是要计算这个数组。
观察这个数组可以知道，kmp可以判断A是否是B的一个子串，并且找到第一个匹配位置？而对于extend[]数组来说，则可以利用它直接解决匹配问题，只要看extend[]数组元素是否有一个等于len_A即可。显然这个数组保存了更多更丰富的信息，即B的每个位置与A的匹配长度。
计算这个数组extend也采用了于kmp类似的过程。首先也是需要计算字符串A与自身后缀的最长公共前缀长度。我们设为next[]数组。当然这里next数组的含义与kmp里的有所过程。但它的计算，也是利用了已经计算出来的next[1…i-1]来找到next[i]的大小，整体的思路是一样的。
首先在1…i-1,要找到一个k，使得它满足k+next[k]-1最大，也就是说，让k加上next[k]长度尽量长。
实际上下面的证明过程中就是利用了每次计算后k+next[k]始终只增不减，而它很明显有个上界，来证明整个计算过程复杂度是线性的。如下图所示，假设我们已经找到这样的k，然后看怎么计算next[i]的值。设len = k+next[k]-1(图中我们用Ak代表next[k]),分情况讨论：
如果len < i 也就是说，len的长度还未覆盖到Ai,这样我们只要从头开始比较A[i…n]与A的最长公共前缀即可，这种情况下很明显的，每比较一次，必然就会让i+next[i]-1增加一.
如果len >= i,就是我们在图中表达的情形，这时我们可以看到i这个位置现在等于i-k+1这个位置的元素，这样又分两种情况
如果 L = next[i-k+1] >= len-i+1,也就是说L处在第二条虚线的位置，这样我们可以看到next[i]的大小，至少是len-i+1,然后我们再从此处开始比较后面的还能否匹配，显然如果多比较一次，也会让i+A[i]-1多增加1.
如果 L < len-i+1 也就是说L处在第一条虚线位置，我们知道A与Ak在这个位置匹配，但Ak与Ai-k+1在这个位置不匹配，显然A与与Ai-k+1在这个位置也不会匹配，故next[i]的值就是L。
这样next[i]的值就被计算出来了，从上面的过程中我们可以看到，next[i]要么可以直接由k这个位置计算出来，要么需要在逐个比较，但是如果需要比较，则每次比较会让k+next[k]-1的最大值加1.而整个过程中这个值只增不减，而且它有一个很明显的上界k+next[k]-1 < 2*len_A,可见比较的次数要被限制到这个数值之内，因此总的复杂度将是O(N)的。
trie树
首先trie树实际上就是一些字符串组成的一个字符查找树，边由代表组成字符串的字符代表，这样我们就可以在O(len(str))时间里判断某个字符串是否属于该集合。trie树的节点内分支可以用链表也可以用数组实现，各有优劣。
简单的trie树每条边由一个字符代表，但是为了节省空间，可以让边代表一段字符，这就是trie的压缩表示。通过压缩表示可以使得trie的空间复杂度与单词节点数目成正比。
AC自动机
ac自动机，可以看成是kmp在多字符串情况下扩展形式，可以用来处理多模式串匹配。只要为这些模式串建立一个trie树，然后再为每个节点建立一个失败指针，也就是类似与kmp的next函数，让我们知道如果匹配失败，可以再从哪个位置重新开始匹配。ac实际上两个人的名字的首字母，Aho-Corasick。
应该还记得，在kmp构造next数组时，我们是从前往后构造，即先构造1…i-1，然后再利用它们计算next[i],这里也是类似。不过这个先后，是通过bfs的顺序来体现的。AC自动机的失败指针具有同样的功能，也就是说当我们的模式串在Tire上进行匹配时，如果与当前节点的关键字不能继续匹配的时候，就应该去当前节点的失败指针所指向的节点继续进行匹配。而从根到这个失败指针指向的节点组成的字符串，实际上就是跟当前节点的后缀的匹配最长的字符串。
rie图
trie图实际上一个确定性自动机，比ac增加了确定性这个属性，对于ac自动机来说，当碰到一个不匹配的节点后可能要进行好几次回溯才能进行下一次匹配。但是对于trie图来说，可以每一步进行一次匹配，每碰到一个输入字符都有一个确定的状态节点。
从上面的图中我们也可以看到trie图的后缀节点跟ac自动机的后缀指针基本一致，区别在于trie图的根添加了了所有字符集的边。另外trie图还会为每个节点补上所有字符集中的字符的边，而这个补边的过程实际上也是一个求节点的后缀节点的过程，不过这些节点都是虚的，我们不把它们加到图中，而是找到它们的等价节点即它们的后缀节点，从而让这些边指向后缀节点就可以了。(比如上图中的黑节点c，它实际上并未出现在我们的初始tire里，但我们可以把它作为一个虚节点处理，把指向它的边指向它的后缀节点)
trie图主要利用两个概念实现这种目的。一个是后缀节点，也就是每个节点的路径字符串去掉第一个字符后的字符串对应的节点。计算这个节点的方法，是通过它父亲节点的后缀节点，很明显它父亲的后缀节点与它的后缀节点的区别就是还少一个尾字符，设为c。所以节点的父节点的指针的c孩子就是该节点的后缀节点。但是因为有时候它父亲不一定有c孩子，所以还得找一个与父亲的c孩子等价的节点。于是就碰到一个寻找等价节点的问题。
而trie图还有一个补边的操作，不存在的那个字符对应的边指向的节点实际上可以看成一个虚节点，我们要找一个现有的并且与它等价的节点，将这个边指向它。这样也实际上是要寻找等价节点。
我们看怎么找到一个节点的等价节点，我们所谓的等价是指它们的危险性一致。那我们再看一个节点是危险节点的充要条件是：它的路径字符串本身就是一个危险单词，或者它的路径字符串的后缀对应的节点是一个危险节点。因此我们可以看到，如果这个节点对应的路径字符串本身不是一个危险单词，那它就与它的后缀节点是等价的。所以我们补边的时候，实际指向的是节点的后缀节点就可以了。
trie图实际上对trie树进行了改进，添加了额外的信息。使得可以利用它方便的解决多模式串的匹配问题。跟kmp的思想一样，trie图也是希望利用现在已经匹配的信息，对未来的匹配提出指导。提出了一些新的概念。定义trie树上，从根到某个节点的路径上所有边上的字符连起来形成的字符串称为这个节点的路径字符串。如果某个节点的路径字符串以一个危险字符串结尾，那么这个节点就是危险节点：也就是说如果到达这个点代表是匹配的状态；否则就是安全节点。 那么如何判断某个节点是否危险呢？
根节点显然是安全节点。一个节点是危险节点的充要条件是：它的路径字符串本身就是一个危险单词，或者它的路径字符串的后缀(这里特指一个字符串去掉第一个字符后剩余的部分)对应的节点(一个字符串对应的节点，是指从trie图中的根节点开始，依次沿某个字符指定的边到达的节点)是一个危险节点。
那么如何求每一个节点的后缀节点呢？这里就可以里利用以前的计算信息，得到了。具体来说就是利用父亲节点的后缀节点，我们只要记住当前节点的最后一个字符设为C，那么父亲节点的后缀节点的C分支节点就是要求的后缀节点了。首先我们限定，根节点的后缀节点是根本身，第一层节点的后缀节点是根节点。这样我们可以逐层求出所有节点的后缀节点。但是这个过程中，可能出现一个问题：父亲节点的后缀节点可能没有c分支。这时候该怎么办呢？
如下图所示如果设当前节点的父亲节点的后缀节点为w，我们假设w具有c孩子为，我们可以看到对于w的整个c子树来说，因为根本不存在通向它们的边c，它们也就不可能是不良字符串，这样这些节点的危险性也就等价与它们的后缀节点的危险性了，而它们的后缀节点，实际上就是w的后缀节点的c孩子，如此回溯下去，最后就能找到。
