字符串在實際中有極為廣泛的應用，在文字編輯、信息檢索、語言編譯等軟件系統中，字符串均是重要的操作對象；在網絡入侵檢測、計算機病毒特征碼匹配以及DNA序列匹配等應用中，都需要進行串匹配，也稱模式匹配。

研究者已收集了大量的病毒DNA和人的DNA數據，想快速檢測出這些人是否感染了相應的病毒。為了方便研究，研究者将人的DNA和病毒DNA均表示成由一些字母組成的字符串序列，然後檢測某種病毒DNA序列是否在患者的DNA序列中出現過，如果出現過，則此人感染了該病毒，否則沒有感染。假設病毒的DNA序列為baa，患者1的DNA序列為aaabbba，則感染，患者2的DNA序列為babbba，則未感染。（注意，人的DNA序列是線性的，而病毒的DNA序列是環狀的）

一、 串的類型定義

串（string）（或字符串）是由零個或多個字符組成的有限序列，一般記為：

s=“ … ”(n≥0)

其中，s是串的名，用雙引号括起來的字符序列是串的值；ai(1≤i≤n)可以是字母、數字或其他字符；串中字符的數目n稱為串的長度。零個字符的串稱為空串（null string），其長度為零。

串的邏輯結構和線性表極為相似，區别僅在于串的數據對象約束為字符集。然而，串的基本操作和線性表有很大差别。在線性表的基本操作中，大多以“單個元素”作為操作對象，例如，在線性表中查找某個元素，求取某個元素，在某個位置上插入一個元素或删除一個元素等；而在串的基本操作中，通常以“串的整體”作為操作對象，例如，在串中查找某個子串，求取一個子串，在串的某個位置上插入一個子串，以及删除一個子串等。

二、串的存儲結構

與線性表類似，串也有兩種基本存儲結構：順序存儲和鍊式存儲。但考慮到存儲效率和算法的方便性，串多采用順序存儲結構。

1、串的順序存儲類似于線性表的順序存儲結構，用一組地址連續的存儲單元存儲串值的字符序列。按照預定義的大小，為每個定義的串變量分配一個固定長度的存儲區，則可用定長數組如下描述：

//串的定長順序存儲結構 #define MAXLEN 255 //串的最大長度 typedef struct{ Char ch[MAXLEN 1]; //串的長度 Int length; }

其中，MAXLEN表示串的最大長度，ch是存儲字符串的一維數組，每個分量存儲一個字符，length表示字符串的當前長度。

為了便于說明，本内容算法描述當中所用到的順序存儲的字符串都是從下标為1的數組分量開始存儲。

以上定義方式是靜态的，在編譯時就确定了串空間的大小。而多數情況下，串的操作是以串的整體形式參與的，串變量之間的長度相差較大，在操作中串值長度的變化也較大，這樣為串變量設定固定大小的空間不盡合理。因此最好是根據實際需要，在程序執行過程中動态地分配和釋放字符數組空間。

在C語言中，存在一個稱之為“堆”（Heap）的自由存儲區，可以為每個新産生的串動态分配一塊實際串長所需的存儲空間，若分配成功，則返回一個指向起始地址的指針，作為串的基址，同時為了以後處理方便，約定串長也作為存儲結構的一部分。這種字符串的存儲方式也稱為串的堆式順序存儲結構，定義如下：

//串的堆式順序存儲結構 Typedef struct{ Char *ch; // 若是非空串，則按串長分配存儲區，否則ch為NULL Int length; }HString;

2、串的鍊式存儲順序串的插入和删除操作不方便，需要移動大量的字符。因此，可采用單鍊表方式存儲串。由于串結構的特殊性——結構中的每個數據元素是一個字符，則在用鍊表存儲串值時，存在一個“結點大小”的問題，即每個結點可以存放一個字符，也可以存放多個字符。

例如，圖（a）所示為結點大小為4（即每個結點存放4個字符）的鍊表：

圖（b）所示為結點大小為1的鍊表。

當結點大小大于1時，由于串長不一定是結點大小的整倍數，則鍊表中的最後一個結點不一定全被串值占滿，此時通常補上“#”或其他的非串值字符（通常“#”不屬于串的字符集，是一個特殊的符号）。

為了便于進行串的操作，當以鍊表存儲串值時，除頭指針外，還可附設一個尾指針指示鍊表中的最後一個結點，并給出當前串的長度。稱如此定義的串存儲結構為塊鍊結構，說明如下：

/* 串的塊鍊存儲結構 */ #define CHUNKSIZE 80 typedef struct Chunk { char ch[CHUNKSIZE]; // 當前塊中的内容 struct Chunk* next; // 指向下一個塊 } Chunk; /* 串的塊鍊存儲類型定義 */ typedef struct { Chunk* head; //串的頭指針 Chunk* tail; //串的尾指針 int length; //串的當前長度 } LString;

在鍊式存儲方式中，結點大小的選擇直接影響着串處理的效率。在各種串的處理系統中，所處理的串往往很長或很多，如一本書的幾百萬個字符，圖書館的成千上萬條目錄，這就要求考慮串值的存儲密度。

顯然，存儲密度小（如結點大小為1時），運算處理方便，然而，存儲占用量大。如果在串處理過程中需進行内、外存交換的話，則會因為内、外存交換操作過多而影響處理的總效率。應該看到，串的字符集的大小也是一個重要因素。一般來說，字符集小，則字符的機内編碼就短，這也影響串值存儲方式的選取。

串值的鍊式存儲結構對某些串操作，如聯接操作等，有一定方便之處，但總地說來，不如順序存儲結構靈活，它占用存儲量大且操作複雜。此外，串值在鍊式存儲結構時，串操作的實現和線性表在鍊表存儲結構中的操作類似，本文不作詳細讨論。

三、串的模式匹配算法

子串的定位運算通常稱為串的模式匹配或串匹配。此運算的應用非常廣泛，比如在搜索引擎、拼寫檢查、語言翻譯、數據壓縮等應用中，都需要進行串匹配。一般采用串的定長順序存儲結構實現的。

串的模式匹配設有兩個字符串S和T，設S為主串，也稱正文串；設T為子串，也稱為模式。在主串S中查找與模式T相匹配的子串，如果匹配成功，确定相匹配的子串中的第一個字符在主串S中出現的位置。

著名的模式匹配算法有BF算法和KMP算法，下面詳細介紹這兩種算法。

1、BF算法

最簡單直觀的模式匹配算法是BF（Brute-Force）算法。模式匹配不一定是從主串的第一個位置開始，可以指定主串中查找的起始位置pos。如果采用字符串順序存儲結構，可以寫出不依賴于其他串操作的匹配算法。

【算法步驟】

① 分别利用計數指針i和j指示主串S和子串T中當前正待比較的字符位置，i初值為pos，j初值為1。

② 如果兩個串均未比較到串尾，即i和j均分别小于等于S和T的長度時，則循環執行以下操作：

S.ch[i]和T.ch[j]比較，若相等，則i和j分别指示串中下個位置，繼續比較後續字符；

若不等，指針後退重新開始匹配，從主串的下一個字符（i=i-j 2）起再重新和子串的第一個字符（j=1）比較。

如果j>T.length，說明子串T中的每個字符依次和主串S中的一個連續的字符序列相等，則匹配成功，返回和子串T中第一個字符相等的字符在主串S中的序号（i-T.length）；否則稱匹配不成功，返回0。

【算法描述】

//返回模式T在主串S中第pos個字符開始第一次出現的位置。若不存在，則返回值為0 //其中，T非空， int Index_BF(SString S,SString T,int pos){ 1≤pos≤S.length i=pos; j=1; //初始化 while(i<=S.length && j<=T.length) //兩個串均未比較到串尾 { if(S[i].ch==T[j].ch) { i; j; } //繼續比較後繼字符 Else{i=i-j 2;j=1;} //指針後退重新開始匹配 } if(j>T.length) return i-T.length; //匹配成功 else return 0; //匹配失敗 }

下圖展示了子串T=“abcac”和主串S的匹配過程（pos=1）。

圖8.1 BF算法的匹配過程

【算法分析】

BF算法的匹配過程容易理解，且在某些應用場合效率也較高。在匹配成功的情況下，考慮以下兩種極端情況。

（1）最好情況下，每趟不成功的匹配都發生在子串的第一個字符與主串中相應字符的比較。例如：

S=“aaaaaba”

T=“ba”

設主串的長度為n，子串的長度為m，假設從主串的第i個位置開始與子串匹配成功，則在前i−1趟匹配中字符總共比較了i−1次；若第i趟成功的字符比較次數為m，則總比較次數為i−1 m。對于成功匹配的主串，其起始位置由1到n−m 1，假定這n−m 1個起始位置上的匹配成功概率相等，則最好的情況下匹配成功的平均比較次數為

（2）最壞情況下，每趟不成功的匹配都發生在模式串的最後一個字符與主串中相應字符的比較。

例如：S=“aaaaaab”

T=“aab”

假設從主串的第i個位置開始與模式串匹配成功，則在前i−1趟匹配中字符總共比較了(i−1) ×m次；若第i趟成功的字符比較次數為m，則總比較次數i ×m。因此最壞情況下匹配成功的平均比較次數為

即最壞情況下的平均時間複雜度是O(n ×m)。BF算法思路直觀簡明。但當匹配失敗時，主串的指針i總是回溯到i−j 2位置，模式串的指針總是恢複到首字符位置j=1，因此，算法時間複雜度高。下面将介紹另一種改進的模式匹配算法。

2、KMP算法

KMP是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同時發現的。其中第一位就是《計算機程序設計藝術》的作者。

KMP算法要解決的問題就是在字符串（也叫主串S）中的模式（pattern）定位問題。說簡單點就是我們平時常說的關鍵字搜索。模式串(子串）就是關鍵字（接下來稱它為T），如果它在一個主串（接下來稱為S）中出現，就返回它的具體位置，否則返回0（常用手段）。

上面用BF算法是沒有問題的，但不夠好！如上面的匹配，A和E不相等，那就把i指針移回第2位（假設下标從1開始），j移動到模式串的第1位，然後又重新開始這個步驟：

如果是人的思維來匹配的話，肯定不會再把i移動回第1位，因為主串匹配失敗的位置前面除了第一個A之外再也沒有A了，我們為什麼能知道主串前面隻有一個A？因為我們已經知道前面三個字符都是匹配的！，而且這4個字符都不相同（這很重要）。移動過去肯定也是不匹配的！有一個想法，i可以不動，我們隻需要移動j即可，如下圖：

上面的這種情況還是比較理想的情況，我們最多也就多比較了再次。但假如是在主串“SSSSSSSSSSSSSA”中查找“SSSSB”，比較到最後一個才知道不匹配，然後i回溯，這個的效率是顯然是最低的。

于是三個大牛研究出了KMP算法。其思想就如同我們上邊所看到的一樣：“利用已經部分匹配這個有效信息，保持i指針不回溯，通過修改j指針，讓模式串盡量地移動到有效的位置。”

所以，假設主串為“s1s2…sn”，子串為“t1t2…tm”，整個KMP的重點就在于當某一個子串字符與主串不匹配時，我們應該知道j指針要移動到哪？

接下來我們自己來發現j的移動規律：

如圖：C和D不匹配了，保持i指針不動，我們要把j移動到哪？顯然是第2位。為什麼？因為前面有一個A與主串中第3個A相同：

如下圖也是一樣的情況：

可以把j指針移動到第3位，因為前面有兩個字母是一樣的：

至此我們可以大概看出一點端倪，當匹配失敗時，j要移動的下一個位置k。存在着這樣的性質：最前面的k個字符和j之前的最後k個字符是一樣的。

如果用數學公式來表示是這樣的：

P[0 ~ k-1] == P[j-k ~ j-1]

這個相當重要，如果覺得不好記的話，可以通過下圖來理解：

這個很重要，我是花了好多時間，才明白為什麼可以直接将j移動到k位置了。這一段隻是為了證明我們為什麼可以直接将j移動到k而無須再比較前面的k個字符。

好，接下來就是重點了，怎麼求這些k呢？因為在子串T的每一個位置都可能發生不匹配，也就是說我們要計算每一個位置j對應的k，所以用一個數組next來保存，next[j] = k，表示當S[i] != T[j]時，j指針的下一個位置。

若令next[j]=k，則next[j]表明當子串中第j個字符與主串中相應字符“失配”時，在子串中需重新和主串中該字符進行比較的字符的位置。由此可引出子串的next函數的定義：

看了很多書，在這個地方都是講得比較含糊或是根本就一筆帶過，甚至就是貼一段代碼上來，為什麼這段代碼是這樣？怎麼确認j指針的下一個位置，根本就沒有說清楚。而這裡恰恰是KMP算法最關鍵的地方。

我們自己來推導思路，現在要始終記住一點，next[j]的值（也就是k）表示，當S[i] != T[j]時，j指針的下一步移動位置。

如何具體推導出一個子串（模式串）的next數組的值？假如：子串：T=”abcac”

分析如下：

（1）當j=1,next[1] = 0;

（2）當j=2，j由1到是j-1就隻有字符“a”，屬于其他情況next[2]=1;

（3）當j=3，j由1到是j-1就隻有字符“ab”，顯然”a”與”b ”不相等，屬于其他情況next[3]=1;

（4）當j=4，j由1到是j-1就隻有字符“aba”，顯然前綴字符”a”，與後綴字符”a”相等，next[4]=2;

（5）當j=5，j由1到是j-1就隻有字符“abaa”，顯然前綴字符”a”，與後綴字符”a”相等，屬于其他情況next[5]=2;

（6）當j=6，j由1到是j-1就隻有字符“abaab”，顯然前綴字符”ab”，與後綴字符”ab”相等，next[6]=3;

（7）當j=7，j由1到是j-1就隻有字符“abaabc”，顯然前綴字符”a”，與後綴字符”c”不相等，屬于其他情況next[7]=1;

（8）當j=5，j由1到是j-1就隻有字符“abaabca”，顯然前綴字符”a”，與後綴字符”a”相等，屬于其他情況next[8]=2;

由此我們可以根據公式得到，如果前後綴一個字符相等，k=next[j]的值就是2，如果兩個字符相等，k=next[j]就是3，後面以些類推。

計算next函數值，算法描述如下：

void get_next(String T,int next[]) {//求子串T的next函數值并存入數組next i=1; j=0； next[1]=0; while(i<T.length) { if(j==0‖T.ch[i]==T.ch[j]){ i; j;next[i]=j; } else j=next[j]; } }

以上面BF算法的匹配過程，我們用KMP算法來推導，next[j]函數值如下：

第一趟，當i=3,j=3時，字符”a”與”c”不相等，

根據上面算法：j= next[j]；得出j = next[3]=1,則next指針下一個值從j=1開始：

i指針繼續右移，j指針也從1開始，當i=7,j=5時，字符”b”與”c”不相等，則j=next[5]=2,則next指針下一個值從j=2開始：

第三趟匹配成功，程序結束，返回匹配位置。

在求得子串的next函數之後，匹配可如下進行：假設以指針i和j分别指示主串和子串中正待比較的字符，令i的初值為pos，j的初值為1。若在匹配過程中si=tj，則i和j分别增1，否則，i不變，而j退到next［j］的位置再比較，若相等，則指針各自增1，否則j再退到下一個next值的位置，依次類推，直至下列兩種可能：

（1）一種是j退到某個next值時字符比較相等，則指針各自增1，繼續進行匹配；

（2）另一種是j退到值為零（即子串的第一個字符“失配”），則此時需将子串繼續向右滑動一個位置，即從主串的下一個字符i 1起和模式重新開始匹配。

KMP算法描述如下：

int Index_KMP(SString S,SString T,int pos) {//利用模式串T的next函數求T在主串S中第pos個字符之後的位置 //其中，T非空，1≤pos≤S.length i=pos;j=1; while(i<=S.length && j<=S.length) //兩個串均未比較到串尾 { if(j==0‖S[i]==T[j]){ i; j;} //繼續比較後繼字符 else j=next[j]; //模式串向右移動 } if(j>T[0]) return i-T[0]; //匹配成功 else return 0; //匹配失敗 }

KMP 匹配算法時間複雜度為O(m)。通常，模式串的長度m比主串的長度n要小得多，因此，對整個匹配算法來說，所增加的這點時間是值得的。

但是，前面定義的next函數在某些情況下尚有缺陷。例如模式“aaaab”在和主串“aaabaaaab”匹配時，當i=4、j=4時s.ch[4]≠t.ch[4]，由next[j]的指示還需進行i=4、j=3，i=4、j=2，i=4、j=1這3次比較。實際上，因為模式中第1～3個字符和第4個字符都相等，因此不需要再和主串中第4個字符相比較，而可以将模式連續向右滑動4個字符的位置直接進行i=5、j=1時的字符比較。

next函數修正值如下：

void get_nextval(String T，int nextval[]) {//求模式串T的next函數修正值并存入數組nextval i=1;nextval［1］=0;j=0; while(i<T.length) { if(j==0‖T.ch[i]==T.ch[j]) { i; j; if(T.ch[i]!=T.ch[j]) nextval[i]=j; else nextval[i]=nextval[j]; } else j=nextval[j]; } }

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!