AC自動機

AC自動機

Aho-Corasick automaton,該算法在1975年產生於貝爾實驗室,是著名的多模匹配算法。 要學會AC自動機,我們必須知道什麼是Trie,也就是字典樹。Trie樹,又稱單詞查找樹或鍵樹,是一種樹形結構,是一種哈希樹的變種。典型套用是用於統計和排序大量的字元串(但不僅限於字元串),所以經常被搜尋引擎系統用於文本詞頻統計。

套用

一個常見的例子就是給出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上進行匹配時,如果與當前節點的關鍵字不能繼續匹配,就應該去當前節點的失敗指針所指向的節點繼續進行匹配。

案例

Problem Description

In the modern time, Search engine came into the life of everybody.Wiskey also wants to bring this feature to his image retrieval system.Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched. To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.

Input

The last line is the description, and the length will be not longer than1000000.

Output

Print how many keywords are contained in the description.

自動機 C++ 原始碼

自動機Pascal模組

POJ1204(AC自動機模板題)

題意:給一個N行長為M的字元串,給你一些需要去匹配的字元串,從任意一個字元串開始可以有八個方向,向上為A,順時針依次是A——H,問你去匹配的字元串在給你的N*M字元串中的坐標是怎么樣的。

代碼:

相關詞條

相關搜尋

熱門詞條

聯絡我們