Java裡用的是indexOf函式，其底層就是字串匹配演算法。其中字串匹配演算法主要包括：

1。 BF（暴力匹配）演算法

1。1概念和原理

Brute Force叫作暴力匹配演算法，也叫樸素匹配演算法。其主要實現原理就是 在主串中，檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串匹配的。

1。2 實現程式碼

public class BFAlth {

public static boolean isMatch（String str，String sub）{

for （int i=0；i<=（str。length（）-sub。length（））；i++）{

// 實際實現是每個字串做字元比較 ，需要迴圈子串

if（str。substring（i，i+sub。length（））。equals（sub））{

return true；

}

}

return false；

}

public static void main（String［］ args） {

System。out。println（isMatch（“hello”，“he”））；

System。out。println（isMatch（“hello”，“el”））；

System。out。println（isMatch（“hello”，“lo”））；

}

}

時間複雜度：每次都比對 m 個字元，要比對 n-m+1 次，所以，這種演算法的最壞情況時間複雜度是 O（n*m） ，其中m為匹配串長度 ，n為主串長度。（注意equals方法也是遍歷字元陣列，所以此處的 時間複雜度是O（n*m））

2。 RK演算法

2。1概念和原理

RK 演算法的全稱叫 Rabin-Karp 演算法，是由它的兩位發明者 Rabin 和 Karp 的名字來命名的。

實現思路：透過雜湊演算法對

主串中的 n-m+1 個子串分別求雜湊值

，然後逐個與

模式串的雜湊值

比較大小。

可以自己根據進位制設計一個演算法，比如數123=1*10^2+2*10^1+3*10^0，字母也可以按照此方式來設計

小寫字母26，可以採用26進位制，大小寫字母52進位制，大小寫字母+數字 62進位制，比如都以小寫字母為例子

abc字串，a的ASCII碼是97，b 98 c99 可以將abc轉換為 97*26^2+98*26^1+99*26^0=65572+2548+99=68219

為了減少數字的大小，去掉偏移量97，改為0*26^2+1*26^1+2*26^0=28，一種簡單的計算hash的方法。

2。2 程式碼實現

public class RKAlth {

/**

* 獲取字串的hash值

* @param s

* @return

*/

public static int strToHash（String s）{

int hash=0；

int length = s。length（）；

for （int i = 0； i < length； i++） {

hash*=26；

hash+=s。charAt（i）-97；

}

return hash；

}

public static boolean isMatch（String str，String sub）{

int hash = strToHash（sub）；

for（int i=0；i<=str。length（）-sub。length（）；i++）{

if （hash==strToHash（str。substring（i，i+sub。length（））））{

return true；

}

}

return false；

}

}

適用於匹配串型別不多的情況，比如：字母、數字或字母加數字的組合 62 （大小寫字母+數字）

3。BM演算法

3。1 概念和原理

BM演算法是在BF演算法基礎之上改進，RK演算法需要設計hash值的演算法，BM（Boyer-Moore）演算法是一種非常高效的字串匹配演算法，滑動演算法。

演算法原理

BM 演算法包含兩部分，分別是壞字元規則（bad character rule）和好字尾規則（good suffix shift）。

壞字元規則

BM 演算法的匹配順序比較特別，它是按照

模式串下標從大到小的順序

，倒著匹配的。從模式串的末尾往前倒著匹配，當發現某個字元沒法匹配的時候，把這個沒有匹配的字元叫作壞字元（主串中的字元）。

字元 c 與模式串中的任何字元都不可能匹配，可以將模式串直接往後滑動三位，將模式串滑動到 c 後面的位置，再從模式串的末尾字元開始比較。

壞字元 a 在模式串中是存在的，模式串中下標是 0 的位置也是字元 a。這種情況下，我們可以將模式串往後滑動兩位，讓兩個 a 上下對齊，然後再從模式串的末尾字元開始，重新匹配

當發生不匹配的時候，

把壞字元對應的模式串中的字元下標記作 si

。如果壞字元在模式串中存在，

把這個壞字元在模式串中的下標記作 xi

。如果不存在，

把 xi 記作 -1

。那模式串往後移動的位數就等於

si-xi

。（下標，都是字元在模式串的下標）

第一次移動 c 在模式串中不存在，xi=-1，si=2，移動位數n=si-xi=3

第二次移動a 在模式串中存在，xi=0，si=2，移動位數n=si-xi=2

好字尾規則

把已經匹配的，拿它在模式串中查詢，如果找到了另一個跟{u}相匹配的子串{u}，那我們就將模式串滑動到子串{u}與主串中{u}對齊的位置

如果在模式串中找不到另一個等於{u}的子串，我們就直接將模式串，滑動到主串中{u}的後面，因為之前的任何一次往後滑動，都沒有匹配主串中{u}的情況。

過度滑動情況：

當模式串滑動到字首與主串中{u}的字尾有部分重合的時候，並且重合的部分相等的時候，就有可能會存在完全匹配的情況。針對這種情況，不僅要看好字尾在模式串中，是否有另一個匹配的子串，還要考察好字尾的字尾子串（c），是否存在跟模式串的字首子串（c）匹配的。

3。2 程式碼實現

壞字元實現程式碼

匹配最佳化

可以用一個長度為256的陣列，來記錄每個字元在模式串中的位置，陣列小標就直接對應ASCII碼的值，陣列的值為字元在模式串中的位置，預設為-1。（ASCII能表示256個字元），如果模式串中有重複的字元，存最後一次出現的字元的位置。

package com。david。stringmatch；

public class BMAlth {

/**

* 初始化模式串的字典陣列

* @param b

* @param dc

*/

private static void generateDc（char［］ b，int［］ dc）{

//初始化字典陣列，每一位存-1

for （int i = 0； i < dc。length； i++） {

dc［i］=-1；

}

for （int i = 0； i < b。length； i++） {

int asc=（int）b［i］；//字元的ASCII碼

dc［asc］=i；//欄位陣列對應的位置存字元在模式串的下標

}

}

/**

* 字串匹配

* @param b 主字串的char陣列

* @param s 模式串的char陣列

* @return 不存在返回-1，存在返回對應的下標

*/

public static int isMatch（char［］ b，char［］ s）{

int m=b。length；//主串的長度

int n=s。length；//模式串的長度

int［］ dc=new int［256］；//模式串字典陣列

//初始化欄位陣列

generateDc（s，dc）；

//i表示主串與模式串對齊的第一個字元

int i=0；

while（i<=m-n）{

//j 壞字元在模式串中的下標

int j；

for（j=n-1；j>=0；j——）{ //從模式串的最後一個字元開始

//主串從正序開始，會加上子串的長度

// a b c d e f

// d e f

//第一次匹配就應該從c開始，所以才有j+i

if （b［j+i］！=s［j］） break；//不匹配

}

//如果j<0，說明模式串中所有字元都匹配成功了

if （j<0）{

return i；//匹配成功，返回主串與模式串第一個匹配的字元的位置

}

//滑動位置計算

// 這裡等同於將模式串往後滑動j-bc［（int）a［i+j］］位

// j：si bc［（int）a［i+j］］：xi 找到主串中匹配的哪個字元，再去字典表找對應字元在

//模式串中的位置從而獲取 xi

i = i + （j - dc［（int）b［i+j］］）；

}

return -1；

}

public static void main（String［］ args） {

System。out。println（isMatch（“abcdefghijklmn”。toCharArray（），“abc”。toCharArray（）））；//0

System。out。println（isMatch（“abcdefghijklmn”。toCharArray（），“lmn”。toCharArray（）））；//11

System。out。println（isMatch（“abcdefghijklmn”。toCharArray（），“efg”。toCharArray（）））；//4

System。out。println（isMatch（“abcdefghijklmn”。toCharArray（），“xxx”。toCharArray（）））；//-1

}

}

3。3 小結

BM演算法的時間複雜度是O（N/M） n：主串長度 m：模式串長度 應用 BM演算法比較高效，在實際開發中，特別是一些文字編輯器中，用於實現查詢字串功能。

4。 Trie樹

4。1 概念和原理

4。1。1 概念

Trie 樹，也叫“字典樹”。它是一個樹形結構。它是一種專門處理字串匹配的資料結構，用來解決在一組字串集合中快速查詢某個字串的問題。Trie 樹的本質，就是利用字串之間的公共字首，將重複的前綴合並在一起 。

其中根節點不包含任何資訊。每個節點表示一個字串中的字元，從根節點到紅色節點的

一條路徑表示一個字串

（紅色節點為葉子節點）。

4。1。2 插入原理

如上圖，每次插入，將字串拆分為字元陣列，從根節點依次查詢，如果不存在，就新增一個節點，如果存在就繼續迴圈，直到插入字串的最後一個字元，將最後一個字元標記為是最終字元（isEnding）。

4。1。3 查詢原理

在 Trie 樹中查詢一個字串的時候，比如查詢字串“her”，那我們將要查詢的字串分割成單個的字元 h，e，r，然後從 Trie 樹的根節點開始匹配。如圖所示，綠色的路徑就是在 Trie 樹中匹配的路徑。

4。1。4 樹結構最佳化

Trie 樹是一個多叉樹，可以透過一個下標與字元一一對映的陣列，來儲存子節點的指標 。如果只考慮小寫字母的話，就26個字母，子節點的陣列長度就26，下標為 0 的位置，儲存指向子節點a 的指標，下標為 1 的位置儲存指向子節點 b 的指標，以此類推，下標為 25 的位置，儲存的是指向的子節點 z 的指標。如果某個字元的子節點不存在，我們就在對應的下標的位置儲存 null。

4。2 程式碼實現

4。2。1 Trie樹節點

class TrieNode{

char data；

TrieNode［］ childs= new TrieNode［26］；

boolean isEndingChar；

public TrieNode（char data） {

this。data = data；

}

}

4。2。1 存和查詢

public class Trie {

private TrieNode root = new TrieNode（‘/’）； // 儲存無意義字元

public void insert（char［］ text）{

TrieNode p=root；

for （int i = 0； i < text。length； i++） {

int index=text［i］-97；

if （p。childs［index］==null）{

p。childs［index］=new TrieNode（text［i］）；

}

//切換到子節點，繼續遍歷新增

p=p。childs［index］；

}

//遍歷完成 p節點肯定是最後一個字元，設定一個結束標記

p。isEndingChar=true；

}

public boolean find（char［］ s）{

TrieNode p = root；

for （int i = 0； i < s。length； i++） {

int index=s［i］-97；

if （p。childs［index］==null）{

return false；

}

//匹配上了，就繼續找下一個節點

p=p。childs［index］；

}

//全部都匹配了，判斷p有沒有結束字元標記 有可能存在 源字元 是 her 查詢字元是he

//這種不算完全匹配，只能算字首匹配

if （p。isEndingChar）{

return true；

}else {

return false；

}

}

public static void main（String［］ args） {

Trie t=new Trie（）；

t。insert（“hello”。toCharArray（））；

t。insert（“her”。toCharArray（））；

t。insert（“hi”。toCharArray（））；

t。insert（“how”。toCharArray（））；

t。insert（“see”。toCharArray（））；

t。insert（“so”。toCharArray（））；

System。out。println（t。find（“how”。toCharArray（）））；//true

System。out。println（t。find（“he”。toCharArray（）））；//false

System。out。println（t。find（“her”。toCharArray（）））；//true

}

}

4。3 小結

時間複雜度

如果要在一組字串中，頻繁地查詢某些字串，用 Trie 樹會非常高效。

構建 Trie 樹的過程，需要掃描所有的字串，時間複雜度是 O(n)

（n 表示所有字串的長度和）。但是一旦構建成功之後，後續的查詢操作會非常高效。每次查詢時，如果要查詢的字串長度是 k，那我們只需要比對大約 k 個節點，就能完成查詢操作。跟原本那組字串的長度和個數沒有任何關係。所以說，

構建好 Trie 樹後，在其中查詢字串的時間複雜度是 O(k)，k 表示要查詢的字串的長度。

典型應用

利用 Trie 樹，實現搜尋關鍵詞的提示功能 我們假設關鍵詞庫由使用者的熱門搜尋關鍵片語成。我們將這個詞庫構建成一個 Trie 樹。當用戶輸入其中 某個單詞的時候，把這個詞作為一個字首子串在 Trie 樹中匹配。為了講解方便，我們假設詞庫裡只有 hello、her、hi、how、so、see 這 6 個關鍵詞。當用戶輸入了字母 h 的時候，我們就把以 h 為字首的 hello、her、hi、how 展示在搜尋提示框內。當用戶繼續鍵入字母 e 的時候，我們就把以 he 為字首的 hello、her 展示在搜尋提示框內。這就是搜尋關鍵詞提示的最基本的演算法原理。