java版的ac多模式匹配演算法的簡單介紹

本文目錄一覽：

• 1、什麼是AC
• 2、串的模式匹配演算法，求編程
• 3、那些經典演算法：AC自動機
• 4、JAVA正則表達式，matcher.find和 matcher.matches的區別

什麼是AC

學術

AC，是academic的縮寫，中文翻譯為「學術」

地理

AC，是Ascension島(阿松森島)的簡稱，位於大西洋南部，靠近非洲，是英國的殖民地

遊戲

1.AC，是英文all combo 的縮寫。一般用在音樂遊戲中,表示全連.

2.在QQ音速中，所做的每一個動作都有一個判定。判定是根據遊戲屏幕中間的節奏點/條來說的，做動作在左右兩節奏點/條剛剛接觸的那一霎那是最佳時期，此時判斷為99%（沒有100%）。若遊戲中每一個動作判定都大於50%，直到遊戲結束。

信息

AC是最早的一種多模式匹配的線性演算法。該演算法應用有限自動機巧妙地將字元比較轉化為了狀態轉移，使得時間複雜度在O(n)，並且與具體模式的長度和模式集的大小無關。

AC在信息學競賽及其訓練中是Accept的縮寫，表示你提交的程序完全符合題目要求並通過了所有數據。

在OIer的心目中，做OJ時，最爽的時候就是AC(取accepted，下同)的時候，因此，這個詞成為了許多OIer心目中最神聖的詞，代表著幸運(又稱RP, RenPin, 人品)。

物理

原子化焓：kJ /mol @25℃

301

熱容：J /（mol· K）

27.2

導熱係數：W/（m·K）

alternating current 中譯為交流電

14.AC:如果是AC220V，則代表是交流電壓220V。

化學

電子親合和能： 0 KJ·mol-1

第一電離能： 0 KJ·mol-1 第二電離能： 0 KJ·mol-1 第三電離能： 0 KJ·mol-1

單質密度： 10.07 g/cm3 單質熔點： 1050.0 ℃ 單質沸點： 3200.0 ℃

原子半徑： 0 埃 離子半徑： 埃 共價半徑： 0 埃

發現人： 德比爾納 時間： 1899 地點： 法國

元素描述：

沉重的銀白色金屬，具有強放射性。

元素來源：

見於所有的鈾礦中，極為稀少。通常在反應器中用中子處理鐳獲得。

元素用途：

沒有什麼實際用途。

元素符號： Ac 英文名： Actinium 中文名： 錒

相對原子質量： 0 常見化合價： 電負性： 0

外圍電子排布： 6d1 7s2 核外電子排布： 2,8,18,32,18,9,2

同位素及放射線： Ac-225[10d] Ac-226[1.2d] Ac-227(放 βα[21.8y]) Ac-228[6.16h]

另外，Ac還是醋酸根(CH3COO-)的簡寫，如NaAc為醋酸鈉(CH3COONa)，HAc為醋酸(CH3COOH)，注意簡寫時Ac要放到後面，

以便與金屬錒區別。

歌星

少年歌星aaron charles carter 名字的縮寫

13歲的亞倫卡特是英國音樂史上擁有連續五首十大金曲的最年輕的歌手，他是「新好男孩」演唱會的特別嘉賓，第一張專輯也在全球各國的十大排行榜上同時也在全球12個國家得到金唱片銷售，第二張專輯更是寫下多項白金唱片的銷售紀錄。

亞倫卡特在2歲的時候就開始學習唱歌及跳舞，7歲的時候就開始組成第一個屬於他自己的樂團。亞倫卡特回憶說：「我在能說話的時候就學會如何唱歌了，我會一面唱歌一面繞著屋子跳著舞。」亞倫卡特很幸運的有一位大哥哥做一個好典範，那就是當今最紅的男孩團體「后街男孩」的成員尼克，尼克的成功無疑的替亞倫卡特開闢了一條康庄大道，從尼克身上他學習了如何在五光十色的娛樂事業中找到一條生存之道。今年13歲的他褪去以往小男孩青澀的感覺，愈發俊秀的臉龐加上充滿活力的演出，成了青少年的新偶像！

亞倫卡特推出最新專輯《0H！AARON》(《天之驕子》)，一推出就登上美國告示牌排行榜的TOP7，而這張專輯除了延續亞倫卡特一貫的HIH0P、RAP、雷鬼音樂風格，更祭出了胞兄———后街男孩成員中的尼克，特別跨刀與亞倫合唱了首支單曲「NOTT00YOUNG，NOTT000LD」以及標題曲「0H！AARON」。專輯中還收錄有「I』MALLABOUTYOU」亞倫卡特首度深情獻唱的抒情曲，及亞倫卡特的小王子白皮書「THEKIDINYOU」，他借著這首歌向全世界宣告：「永遠會以音樂喚醒所有聆聽者心中沉睡的青春活力！」

8.是Associazione Calcio Milan s.p.a

球隊

義大利語AC是足球俱樂部的簡稱,就像英語中的FC一樣

所以AC Milan實際上應翻譯成米蘭足球俱樂部,簡稱米蘭隊.AC Milan是最先翻譯進來的,也就一直保留了下來

魔獸世界中定義

AC – Armor Class，盔甲級別或防禦。

魔獸爭霸中及其戰報中表精靈族弓箭手（Archer）

中國國際航空公司

AC= Air China 中國國際航空公司

AC」在英漢詞典中的解釋(來源:百度詞典)：

AC

abbr.

1. =alternating current

2. =air-conditioning 空氣調節(裝置)

Ac

abbr.

1. =[Bible] Acts

ac

abbr.

1. =air conditioning 空調

2. =average cost 平均支出

3. =alternating current 交流(電)

4. =automatic analog computer 自動模擬電腦

串的模式匹配演算法，求編程

#includestdio.h

void getnext(const char c[],int next[])

{

int j=0,k=-1;

next[0]=-1;

while(c[j]!=’\0′)

{

if(k==-1||c[j]==c[k])

{

j++;

k++;

if(c[j]!=c[k])

next[j]=k;

else

next[j]=next[k];

}

else

k=next[k];

}

}

int KMP(const char *Text,const char* Pattern) //const 表示函數內部不會改變這個參數的值。

{

if( !Text||!Pattern|| Pattern[0]==’\0′ || Text[0]==’\0′ )//

return -1;//空指針或空串，返回-1。

int len=0;

const char * c=Pattern;

while(*c++!=’\0′)//移動指針比移動下標快。

{

++len;//字元串長度。

}

int *next=new int[len+1];

getnext(Pattern,next);//求Pattern的next函數值

int index=0,i=0,j=0;

while(Text[i]!=’\0′ Pattern[j]!=’\0′ )

{

if(Text[i]== Pattern[j])

{

++i;// 繼續比較後繼字元

++j;

}

else

{

index += j-next[j];

if(next[j]!=-1)

j=next[j];// 模式串向右移動

else

{

j=0;

++i;

}

}

}

delete []next;

if(Pattern[j]==’\0′)

return index;// 匹配成功

else

return -1;

}

int main()

{

char clong[100],cshort[20]=”abcac”;

int next[20];

scanf(“%s”,clong);

scanf(“%s”,cshort);

printf(“%d”,KMP(clong,cshort));

}

那些經典演算法：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，如後面的圖。

JAVA正則表達式，matcher.find和 matcher.matches的區別

1.find()方法是部分匹配，是查找輸入串中與模式匹配的子串，如果該匹配的串有組還可以使用group()函數。

matches()是全部匹配，是將整個輸入串與模式匹配，如果要驗證一個輸入的數據是否為數字類型或其他類型，一般要用matches()。

2.Pattern pattern= Pattern.compile(“.*?,(.*)”);

Matcher matcher = pattern.matcher(result);

if (matcher.find()) {

return matcher.group(1);

}

3.詳解：

matches

public static boolean matches(String regex, CharSequence input)

編譯給定正則表達式並嘗試將給定輸入與其匹配。

調用此便捷方法的形式

Pattern.matches(regex, input);

Pattern.compile(regex).matcher(input).matches() ;

如果要多次使用一種模式，編譯一次後重用此模式比每次都調用此方法效率更高。

參數：

regex – 要編譯的表達式

input – 要匹配的字元序列

拋出：

PatternSyntaxException – 如果表達式的語法無效

find

public boolean find()嘗試查找與該模式匹配的輸入序列的下一個子序列。

此方法從匹配器區域的開頭開始，如果該方法的前一次調用成功了並且從那時開始匹配器沒有被重置，則從以前匹配操作沒有匹配的第一個字元開始。

如果匹配成功，則可以通過 start、end 和 group 方法獲取更多信息。

matcher.start() 返回匹配到的子字元串在字元串中的索引位置.

matcher.end()返回匹配到的子字元串的最後一個字元在字元串中的索引位置.

matcher.group()返回匹配到的子字元串

返回：

當且僅當輸入序列的子序列匹配此匹配器的模式時才返回 true。