模式匹配隨機演算法例子

A. 那些經典演算法：AC自動機

第一次看到這個名字的時候覺得非常高級，深入學習就發現，AC就是一種多模式字元串匹配演算法。前面介紹的BF演算法，RK演算法，BM演算法，KMP演算法都屬於單模式匹配演算法，而Trie樹是多模式匹配演算法，多模式匹配演算法就是在一個主串中查找多個模式串，舉個最常用的例子，比如我們在論壇發表評論或發帖的時候，一般論壇後台會檢測我們發的內容是否有敏感詞，如果有敏感詞要麼是用***替換，要麼是不讓你發送，我們評論是通常是一段話，這些敏感詞可能成千上萬，如果用每個敏感詞都在評論的內容中查找，效率會非常低，AC自動機中，主串會與所有的模式串同時匹配，這時候就可以利用AC自動機這種多模式匹配演算法來完成高效的匹配，

AC自動機演算法是構造一個Trie樹，然後再添加額外的失配指針。這些額外的適配指針准許在查找字元串失敗的時候進行回退（例如在Trie樹種查找單詞bef失敗後，但是在Trie樹種存中bea這個單詞，失配指針會指向前綴be），轉向某些前綴分支，免於重復匹配前綴，提高演算法效率。
常見於IDS軟體或病毒檢測軟體中病毒特徵字元串，可以構建AC自動機，在這種情況下，演算法的時間復雜度為輸入字元串的長度和匹配數量之和。

假設現有模式字元串集合：{abd,abdk, abchijn, chnit, ijabdf, ijaij} 構建AC自動機如下：

說明：

1）當前指針curr指向AC自動機的根節點：curr=root。
2）從文本串中讀取（下）一個字元。
3）從當前節點的所有孩子節點中尋找與該字元匹配的節點：

4）若fail == null，則說明沒有任何子串為輸入字元串的前綴，這時設置curr = root，執行步驟2.
若fail != null,則將curr指向 fail節點，指向步驟3。
理解起來比較復雜，找網上的一個例子，假設文本串text = 「abchnijabdfk」。
查找過程如下：

說明如下：
1）按照字元串順序依次遍歷到：a-->b-->c-->h ,這時候發現文本串中下一個節點n和Trie樹中下一個節點i不匹配，且h的fail指針非空，跳轉到Trie樹中ch位置。
注意c-->h的時候判斷h不為結束節點，且c的fail指針也不是結束節點。
2）再接著遍歷n-->i,發現i節點在Trie樹中的下一個節點找不到j，且有fail指針，則繼續遍歷，
遍歷到d的時候要注意，d的下一個匹配節點f是結束字元，所以得到匹配字元串：ijabdf，且d的fail節點也是d，且也是結束字元，所以得到匹配字元串abd，不過不是失敗的匹配，所以curr不跳轉。

先將目標字元串插入到Trie樹種，然後通過廣度有限遍歷為每個節點的所有孩子節點找到正確的fail指針。
具體步驟如下：
1）將根節點的所有孩子節點的fail指針指向根節點，然後將根節點的所有孩子節點依次入隊列。
2）若隊列不為空：
2.1）出列一個字元，將出列的節點記為curr，failTo表示curr的
fail指針，即failTo = curr.fail 。
2.2) 判斷curr.child[i] == failTo.child[i]是不是成立：
成立：curr.child[i].fail = failTo.child[i]
因為當前字元串的後綴和Tire樹的前綴最長部分是到fail，
且子字元和failTo的下一個字元相同，則fail指針就是
failTo.child[i]。
不成立： 判斷failTo是不是為null是否成立：
成立： curr.child[i].fail = root = null。
不成立： failTo = failTo.fail 繼續2.2
curr.child[i]入列，再次執行步驟2）。
3）隊列為空結束。

每個結點的fail指向的解決順序是按照廣度有限遍歷的順序完成的，或者說層序遍歷的順序進行，我們根據父結點的fail指針來求當前節點的fail指針。

上圖為例，我們要解決y節點的fail指針問題，已經知道y節點的父節點x1的fail是指向x2的，根據fail指針的定義，我們知道紅色橢圓中的字元串序列肯定相等，而且是最長的公共部分。依據y.fail的含義，如果x2的某個孩子節點和節點y表示的表示的字元相等，y的fail就指向它。
如果x2的孩子節點中不存在節點y表示的字元。由於x2.fail指向x3，根據x2.fail的含義，我們知道綠色框中的字元序列是相同的。顯然如果x3的某個孩子和節點y表示字元相等，則y.fail就指向它。

如果x3的孩子節點不存在節點y表示的字元，我們重復這個步驟，直到xi的fail節點指向null，說明我們達到頂層，只要y.fail= root就可以了。
構造過程就是知道當前節點的最長公共前綴的情況下，去確定孩子節點的最長公共前綴。

下圖中，每個節點都有fail虛線，指向根節點的虛線沒畫出，求圖中c的孩子節點h的fail指向：

原圖中，深藍色的框出來的是已經確定fail指針的，求紅色框中h節點的fail指針。
這時候，我們看下h的父親節點c的fail指針指向，為ch中的c（這表示abc字元串的所有後綴bc和c和Trie樹的所有前綴中最長公共部分為c），且這個c節點的孩子節點中有字元為h的字元，所以圖中紅色框中框出的h節點的fail指針指向 ch字元串中的h。

求紅色框中i的fail指針指向，上圖中，我們可以看到i的父親節點h的指向為ch中的h，（也就是說我們的目標字元串結合中所有前綴和字元序列abch的所有後綴在Trie樹中最長前綴為ch。）我們比較i節點和ch中的h的所有子節點，發現h只有一個n的子節點，所以沒辦法匹配，那就繼續找ch中h的fail指針，圖中沒畫出，那麼就是它的fail指針就是root，然後去看root所有子節點中有沒有和i相等的，發現最右邊的i是和我們要找的i相等的，所以我們就把i的fail指針指向i，如後面的圖。

B. 數據結構與演算法——字元串匹配問題(KMP演算法)

KMP演算法也是比較著名的模式匹配演算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 發表的一個模式匹配演算法。可以大大避免重復遍歷的情況。

如果使用暴風演算法的話，前面五個字母完全相等，直到第六個字母 "f" 和 "x" 不相等。如下圖：

T = 「abcdex」
j 123456
模式串 abcdex
next[j] 011111

T = "abcabx"
j 123456
模式串T abcabx
next[j] 011123

T = "ababaaaba"
j———————123456789
模式串T——— ababaaaba
next[j]————011234223

T = "aaaaaaaab"
j———————123456789
模式串T——— aaaaaaaab
next[j]————012345678

next數組其實就是求解字元串要回溯的位置
假設，主串S= 「abcababca」;模式串T=「abcdex」，由以上分析得出next數組為011111，next數組意味著當主串與模式串不匹配時，都需要從第一個的位置重新比較。

KMP演算法也是有缺陷的，比如主串S=「aaaabcde」,模式串T= 「aaaaax」。next的數組就是012345；

當開始匹配時，當i= 5，j = 5時，我們發現字元"b"與字元「a」不相等，如上圖，j = next[5] = 4;

由於T串的第二、三、四、五位置的字元都與首位「a」相等，那麼可以用首位next[1]的值去取代與它相等的後續字元的next[j],那麼next數組為{0,0,0,0,0,5};

在求解nextVal數組的5種情況

C. 串模式匹配演算法（C語言）100分懸賞

第一個樸素演算法:
1.普通的串模式匹配演算法:
int index(char s[],char t[],int pos)
/*查找並返回模式串T在S中從POS開始的位置下標,若T不是S的子串.則返回-1.*/
{
int i,j,slen,tlen;
i=pos;j=0; //i,j分別指示主串和模式串的位置.
slen=strlen(s);tlen=strlen(t); //計算主串和模式串的長度.
while(i<slen && j<tlen)
{
if(s[i]==t[j]) {i++;j++;}
else {i=i-j+1;j=0;}
}
if(j>=tlen) return i-tlen;
return -1;
}

第二個KMP演算法.該演算法支持從主串的任意位置開始搜索.
2.KMP演算法:
//求模式串的next函數.
void get_next(char *p,int next[])
{
int i,j,slen;
slen=strlen(p);i=0;
next[0]=-1;j=-1;
while(i<slen)
{
if(j==-1||p[i]==p[j]) {++i;++j;next[i]=j;}
else j=next[j];
}
}

//KMP模式匹配演算法
int index_kmp(char *s,char *p,int pos,int next[])
/* 利用模式串P的NEXT函數,求P在主串S中從第POS個字元開始的位置*/
/*若匹配成功.則返回模式串在主串中的位置下標.否則返回-1 */
{
int i,j,slen,plen;
i=pos-1;j=-1;
slen=strlen(s);plen=strlen(p);
while(i<slen && j<plen)
{
if(j==-1||s[i]==p[j]) {++i;++j;}
else j=next[j];

D. 數據結構-串的模式匹配

串的模式匹配就是子串定位操作。給定兩明虧個串s="s0 s1 ... s(n-1)"和t="t0 t1 ... t(m-1)"（其中n和m分別是串s和t的長度），在主串s中尋找子串t的過程稱為模式匹配，t稱為模式。如果在s中找到等於t的子串，則稱匹配成功，返回t在s中的首次出現的下標位置；否則匹配失敗，返回-1。

本文介紹三個串模式匹配演算法，分別是簡單回溯演算法（Brute-Force，BF演算法）、KMP演算法、KMP演算法的改進。

從主串s的第0個字元開始，與模式串t的第0個字元開始逐字元比較，不相同時回溯到模式串t的第0個和主串s的第1個字元，重新開始比較。以此類推，直到t的所有字元完成匹配，則匹配成功，否則匹配失敗。

BF演算法速度慢的原因是存在大量不必要的回溯，即在某一趟與t的匹配過程失敗後，需要返回s串開始字元的下一字元重新開始比較，這對於某些模式串t來說是不必要的。例如，若s=12123123132，t=12313，在t與12 12312 3132中加粗子序列進行比較時，在 2 處發生失配，BF演算法接下來將t與121 23123 132、1212 31231 32、12123 12313 2比較。由於t中的231、312與其開始的123並不相同，顯然t與121 23123 132、1212 31231 32的比較是不必要的。

KMP演算法就是利用模式串中與模式串開頭部分子串的重復性來減少重復回溯，實現新一輪比較的直接跳轉。 具體來說，KMP演算法利用一個數組記錄模式串中每一個字元前面有幾個字元與模式串從頭重復，在與s串比較失配時，直接跳轉到重復子串的下一個字元繼續比較，而不用跳轉至模式串t的第0個字元。

演算法步驟： ①計算跳轉數組next。②利用KMP演算法進行模式匹配。

next數組通過遞推計算，即如果當前字元 t[j] 的前一個字元 t[j-1] 與其 next[j-1] 指向的字元 t[next[j-1]] 相同，意味著 t[j] 前的 next[j-1]+1 個字元與從 t[0] 到 t[next[j-1]] 的子串相同，因此 next[j]=next[j-1]+1 ；如果不相同，則遞推至 t[next[j-1]] 的next值指向的字元，與 t[j-1] 比較，直到確認 t[j] 前與 t 串從頭重復的數羨字元數，或者無重復字元標記為薯槐拍 0 。

注意此處的函數返回參數類型為int*，用於 返回一位數組 ，且返回的這個一位數組必須在函數中用static定義。

KMP演算法進行模式匹配時，只需在回溯時將 j 指針賦值為 next[j] 。需要注意的是，若 next[j] 為 -1 ，則意味著 t[j] 前面沒有與 t 從頭重復的字元，且 t[j] 與 s[i] 失配，則 i 和 j 均加 1 。

考慮更特殊的模式串，還能進一步減少不必要的回溯次數。例如，s=111211112，t=11112，按照上述next的計算方式，next={-1,0,1,2,3}。當 i=3, j=3 時失配，此時 s[i]=2, t[j]=1 ，由於 next[j]=2 ，於是 j 跳轉為 2 ，t=11 1 12與s=111 2 11112比較。由於 t[next[j]]=t[j] 也為 1 ，必然與 s[i]=2 不相同，顯然這次回溯也不必要。

總結來說， 當失配的字元與待跳轉的字元相同時，跳轉一步並無意義，可再跳一步 ，即將當前字元置為跳轉後字元的next值。

E. 隨機化演算法的舉例

下面，我們就隨機化問題，舉一個例子：
一個長度在4..10的字元串中，需要判定是否可以在字元串中刪去若干字元，使得改變後字元串符合以下條件之一：
（1）AAAA；（2）AABB；（3）ABAB；（4）ABBA。
例如：長度為6字元串「POPKDK」，若刪除其中的「O」，「D」兩個字母，則原串變為：「PPKK」，符合條件（2）AABB。
分析：
這道題很容易想到一種演算法：運用排列組合：枚舉每4個字母，然後逐一判斷。演算法是可行的，但是如果需要題目中加上一句話：需要判斷n個字元串，且n<=100000，那麼這樣的耗時是不能讓人忍受①的，因為在枚舉的過程中，是非常浪費時間的。
（①：這里是指信息學中要求演算法的普遍運算時間為：1000ms）
所以這道題有可能可以藉助於隨機化演算法，下面我們來算一下在10個字元中取4個字元一共有多少種取法：C(4,10)=210。那麼很容易得知，隨機化演算法如果隨機300次，能得到的結果基本上就正確了(概率為1-(209/210)^300，約為0.76)，而隨機時的時間消耗是O(1)，只需要判斷沒有隨機重復即可，判重的時間復雜度也為O(1)，並且最多隨機300次，這樣就可以有效地得到答案，最大運算次數為：O(300n)，這是在計算機的承受范圍內（1000ms）的。
從這里就能看出，隨機化演算法是一個很好的概率演算法，但是它並不能保證正確，而且它單獨使用的情況很少，大部分是與其他的演算法：例如貪心、搜索等配合起來運用。 排序問題。快速排序是排序方法中較為便捷的方法之一，但是由於它極不穩定，最好的時候時間復雜度為O(n㏒n)，這里的㏒是指以2為底的對數運算。最壞的時候能達到與普通排序方法一樣的O(n^2)。
而制約快速排序的有兩個：一是數據，越無序的數據，快排的速度越快；二是中間點的枚舉。
因為兩個制約條件都與隨機有著不可分開的關系。
所以，在快速排序中加入隨機化演算法無疑是十分重要的。
運用在：
（1）數據讀入時，隨機排放數據位置。
（2）中間點的枚舉進行多次隨機化後決定。
這樣就基本上將快速排序的時間復雜度維持在最好狀態。