1、算法流程圖
（1） void Init()
此函數是初始化函數，用來給fail數組和goto數組初始化值。
（2） void GotoFunction(string x)
這個函數的作用是生成有限自動機狀態轉移圖。
(3) void FailFunction(int target,int k)
這是fail函數，核心內容是求出每個狀態的fail值。
(4) void UpdateOutput()
這是update輸出函數。其作用是更新每個狀態的輸出值。
（5）void Check(string x)
這個是check函數，其作用是判斷改狀態下output函數是否有輸出，如果有輸出就輸出相應狀態下的字符串。並且決定該狀態接受輸入之後的去向，如果fail，則調用該狀態的fail 函數來決定去向。
（6）int main()
主函數，整個過程的入口。
2、自動機所定義的數據結構及其功能
（1） int Goto[M][26];
goto數組是狀態機狀態的載體，內部存儲著本次實驗的全部狀態。起始狀態為0，之後每獲得一個有效輸入就生成一個新的狀態。但是在生成狀態之前要進行檢驗，看是否已經存在本次狀態。
（2） int Fail[M];
fail數組存儲的是該狀態獲得輸入後，如果結果為fail之後的轉向狀態。
（3） string Output[M];
output數組是一個字符串數組，存儲的是以該狀態為終結狀態的字符串。當然，字符串不唯一，AC算法的核心任務之一就是找到每個狀態為終結狀態時候的全部輸出字符串。
（4） string Depth[M];
depth數組用來標示該狀態在第幾層。我們在此次實驗中將goto函數創建的狀態看作一個樹，因此必然需要一個數組來指明樹中的節點所在的層數。
3、轉向函數、失效函數、輸出函數的構建過程
（1） 轉向函數
我們首先來看其偽代碼：
結合偽代碼和剛才的函數流程圖，我們可以看出轉向函數首先對數組進行初始化。其次，來看while循環。如果g(state,aj)!=fail，那麼就將g(state,aj)賦值給state，其目的是如果已經存在的狀態就不必再次創建，只需要不斷地向前更新狀態即可。可是如果g(state,aj)=fail，那麼我們就要創建新的狀態，即newstate+1，並將g(state,aj)指向此狀態，再更新狀態。在函數最後，構建部分output函數。
（2） 失效函數
我們來看fail函數的偽代碼：
Fail函數采用隊列作為核心數據結構。首先將0狀態後的有效狀態加入隊列。如果隊列不空，就會一直執行while循環中的代碼。首先將隊首取出，將隊首能夠到達的有效狀態依次加入隊列。求出已取出的隊首的fail值並作為state。接下來判斷g(state,a)是否為fail。如果不是fail，那麼該值就會作為新入隊列的隊首的fail值。依次類推，用隊列以層序的方式將狀態圖中每一個狀態的fail值都求出來。求出了改狀態的fail值之後，應該將此狀態的輸出並上fail狀態的輸出。這是很關鍵的一步，用以更新output數組輸出值。
（3） 輸出函數
同樣我們來看看output函數的偽代碼
Output本質就是在模擬自動機執行的過程。首先進入while循環，如果g(state,a)為fail，那麼就調用改狀態的fail函數，並將函數值更新給state。直到跳出while循環，之後狀態往前走一步，並判斷改狀態是否有輸出。如果有輸出，就先將改狀態的輸出打印出來，再繼續讀入下一個輸入。
4、 源代碼
#include<iostream>
#include<string.h>
#define M 20//State_Number
using namespace std;
int Goto[M][26];
int Top;
int Fail[M];
string Output[M];
string Depth[M];
void Init()
{
Top=0;
for(int i=0;i<M;i++)
{
Fail[i]=0;
for(int j=0;j<26;j++)
{
Goto[i][j]=0;
}
Depth[i]=Output[i]="";
}
Depth[0]+='0';
}
void GotoFunction(string x)
{
int len=x.length();
int next=0;
for(int i=0;i<len;i++)
{
int index=x[i]-97;/*a->0*/
if(Goto[next][index]==0)
{
Goto[next][index]=++Top;
next=Top;
}
else
{
next=Goto[next][index];
}
char num=next+48;/*0->'0'*/
if(Depth[i+1].find(num)==Depth[i+1].npos)
{
/*
這段代碼很巧妙，他本質上是用一個數組來模擬樹
其作用是讓i+1層囊括這一層的所有狀態
*/
Depth[i+1]+=num;//每一層都有哪些狀態
}
}
Output[next]+=x;//構建output數組，在next位置輸出x字符串
}
void FailFunction(int target,int k)
{
for(int i=0;i<Depth[k].length();i++)
{
int num=Depth[k][i]-48;
for(int j=0;j<26;j++)
{
if(Goto[num][j]==target)
{
/*
這一段是核心代碼
首先找到state
然後根據算法構建target的fail值
*/
int state=Fail[num];
Fail[target]=Goto[state][j];
return;
}
}
}
}
void UpdateOutput()
{
int k=2,num;
Fail[0]=0;
for(int i=0;i<Depth[1].length();i++)
{
num=Depth[1][i]-48;
Fail[num]=0;//當然啦，我們規定層數為一的狀態fail函數值都為0
}
while(Depth[k]!="")
{
for(int i=0;i<Depth[k].length();i++)
{
num=Depth[k][i]-48;
FailFunction(num,k-1);
/*
這一段是核心代碼
就好像廣度優先遍歷
對於每一層的每一個狀態
構建其fail函數值
*/
if(Output[Fail[num]]!="")
{
Output[num]+=" ";
Output[num]+=Output[Fail[num]];
/*
當然這也是核心代碼
重構output內部值
*/
}
}
k++;
}
for(int i=0;i<=Top;i++)
{
cout<<'\n'<<i<<'\t'<<Output[i];
}
}
void Check(string x)
{
int state=0,index,i=0;
while(i<x.length())
{
index=x[i]-97;
if(Goto[state][index]!=0||state==0)
{
/*
0狀態��論輸入什麼都不報錯
*/
state=Goto[state][index];
if(Output[state]!="")
{
cout<<i+1<<'\t'<<Output[state]<<'\n';
}
i++;
}
else
{
state=Fail[state];
}
}
}
int main()
{
Init();
int i=1;
cout<<"welcome the AC world!"<<endl;
cout<<"please input the "<<i <<" patterns: ";
string x;
cin>>x;
while(x!="exit")
{
i++;
cout<<"please input the "<<i <<" patterns: ";
GotoFunction(x);
cin>>x;
}
UpdateOutput();
cout<<"\n\n";
cin>>x;
Check(x);
}
