AC自動機（hdu2222）

AC自動機

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

AC自動機其實是Trie樹和KMP算法的集合體，

首先要有這兩個算法基礎才能更好的了解AC自動機的核心所在。

字典樹查找比對串，當失配時，利用如同KMP中next數組一樣的失敗指針，去找下一個比對節點

避免了每次都從根節點周遊的尴尬

大大減少了時間複雜度。

具體的思想可以參見此視訊講解的比較清楚，比看大部分部落格了解起來都快

http://www.bilibili.com/video/av6295004/#page=1

(夭壽了！！！我竟然在B站看算法視訊)

講的不錯。

給出模闆題

hdu2222

Keywords Search

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 61692    Accepted Submission(s): 20399

Problem Description In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.

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 First line will contain one integer means how many cases will follow by.

Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)

Each keyword will only contains characters 'a'-'z', and the length will be not longer than 50.

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

Output Print how many keywords are contained in the description.  

Sample Input

1
5
she
he
say
shr
her
yasherhs
          

Sample Output

3
          

查找比對串含有的單詞數

代碼給出詳細的注釋，比較易懂

本題可作為刷題模闆

#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
#include<stdlib.h>

using namespace std;

#define MAX_N 1000006
#define MAX_Tot 500005

struct ACo{
	struct state{
		//子節點數組 
		int next[26];
		//目前節點的失敗指針 
		int fail;
		//到目前位置的字元串結束個數 
		int cnt;
		
	}stateTable[MAX_Tot];
	
	//目前AC自動機樹的節點個數 
	int size; 
	queue<int> que;
	//初始化 
	void init()
	{
		//将節點初始化 
		while(que.size()) que.pop();
		for(int i=0;i<MAX_Tot;i++)
		{
			memset(stateTable[i].next,0,sizeof(stateTable[i].next));
			stateTable[i].fail = 0;
			stateTable[i].cnt = 0; 
		}
		//根節點一定存在，是以節點個數為1 
		size = 1;
	} 
	
	//建構字典樹 
	void insert(char *str)
	{
		int n = strlen(str);
		int now = 0;
		for(int i=0;i<n;i++)
		{
			char c = str[i];
			//如果到目前節點子節點不存在的話 
			if(!stateTable[now].next[c-'a'])
			{
				//開辟新節點，并将節點個數加一，注意size從1開始的 
				stateTable[now].next[c-'a'] = size++;
			}	
			//每次都要進行走到下一節點 
			now = stateTable[now].next[c-'a'];
			
		} 
		//該字元串便利完之後走到的節點 
		stateTable[now].cnt++;
	} 
	//構造失配指針 
	void build()
	{
		
		//根節點的失配指針設為-1 
		stateTable[0].fail = -1;
		//将根節點壓入隊列 
		que.push(0);
		
		while(que.size())
		{
			//取目前隊列中的第一個，即廣度優先周遊數，保證每層節點的失敗指針都選擇完成，才有可能繼續下一層
			//否則，如果深度優先周遊會導緻指針不為最優，因為别的叉沒有被構造。 
			int u = que.front();
			//取一個，要将其彈出 
			que.pop();
			
			//将目前節點的所有子節點周遊 
			for(int i=0;i<26;i++)
			{
				//如果目前節點的子節點之一存在子節點 
				if(stateTable[u].next[i])
				{
					//判斷目前點是否為根節點 
					if(u==0)
					{
						//如果為根節點，沒辦法，隻能讓目前節點的子節點的失敗指針指向0，即指向根節點 
						//根節點的第一層節點都滿足，可以想一下。 
						stateTable[stateTable[u].next[i]].fail = 0;
					}
					//否則 
					else
					{
						//記錄目前節點的失敗指針 
						int v = stateTable[u].fail;
						//如果失敗指針存在的話 
						while(v!=-1)
						{
							//并且其失敗指針節點也存在子節點 
							if(stateTable[v].next[i])
							{
								//将目前節點 的 失敗指針 指向其 失敗指針節點 的下一個節點 
								stateTable[stateTable[u].next[i]].fail = stateTable[v].next[i] ;
								break;
							}
							//記錄下失敗指針的位置。 
							v = stateTable[v].fail; 
						}
						//如果找了半天，其各種祖先節點的失敗指針仍然不存在 
						if(v==-1)
						{
							//隻能将目前節點的失敗指針指向根節點 
							stateTable[stateTable[u].next[i]].fail = 0;
						}
					}
					//将目前節點入隊列，畢竟要廣搜一層來确定 
					que.push(stateTable[u].next[i]);
				}
			}
		}
		
	}
	int Get(int u)
	{
		int res = 0;
		while(u)
		{
			//目前節點的不為根節點
			//res+上目前節點下的單詞數 
			res = res+stateTable[u].cnt;
			//目前節點單詞數清零，避免一條子樹下重複加值 
			stateTable[u].cnt = 0;
			//回溯其失敗指針下滿足條件的單詞數 
			u = stateTable[u].fail;
		}
		return res;
	}
	//制造比對函數 
	int match(char *S)
	{
		int n = strlen(S);
		int res = 0,now = 0;
		for(int i=0;i<n;i++)
		{
			char c = S[i];
			//存在自不必多說，向下一個指針移動 
			if(stateTable[now].next[c-'a'])
			{
				now = stateTable[now].next[c-'a']; 
			}
			else
			{
				//一旦失配，不回溯根節點，而是回溯失敗指針節點 
				int p = stateTable[now].fail;
				//如果失配指針存在，或者失配指針指向的根節點存在 
				while(p!=-1 && stateTable[p].next[c-'a']==0)
				{
					//更新失敗指針的位置，即不=停的向父節點靠攏 
					p = stateTable[p].fail;
				}
				//如果隻能找到根節點，那就從根節點進行比對 
				if(p==-1)
				{
					now = 0;
				}
				else{
					//不然，目前節點跳到失敗節點的存在子節點 
					now = stateTable[p].next[c-'a'];
				}
			}
			//如果目前節點下存在的單詞數不為0 
			if(stateTable[now].cnt)
			{
				//記錄到目前節點為止所有含有的父節點（失敗節點）的單詞數， 
				res +=Get(now);
			}
		}
		return res;
	}
}aho;
int T;
int n;
char S[MAX_N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		aho.init();
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			scanf("%s",S);
			aho.insert(S);
		}
		aho.build();
		scanf("%s",S);
		printf("%d\n",aho.match(S));
	}
 }