當前位置:成語大全網 - 英語詞典 - AC自動機的概述

AC自動機的概述

應用

壹個常見的例子就是給出n個單詞,再給出壹段包含m個字符的文章,讓妳找出有多少個單詞在文章裏出現過。

要搞懂AC自動機,先得有模式樹(字典樹)Trie和KMP模式匹配算法的基礎知識。AC自動機算法分為3步:構造壹棵Trie樹,構造失敗指針和模式匹配過程。

如果妳對KMP算法了解的話,應該知道KMP算法中的next函數(shift函數或者fail函數)是幹什麽用的。KMP中我們用兩個指針i和j分別表示,A[i-j+ 1..i]與B[1..j]完全相等。也就是說,i是不斷增加的,隨著i的增加j相應地變化,且j滿足以A[i]結尾的長度為j的字符串正好匹配B串的前 j個字符,當A[i+1]≠B[j+1],KMP的策略是調整j的位置(減小j值)使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配,而next函數恰恰記錄了這個j應該調整到的位置。同樣AC自動機的失敗指針具有同樣的功能,也就是說當我們的模式串在Trie上進行匹配時,如果與當前節點的關鍵字不能繼續匹配,就應該去當前節點的失敗指針所指向的節點繼續進行匹配。