串類型的定義串的表示和實現(xiàn)串的模式匹配算法串操

1、1 物料管理STRG1Programing and Data Structures: String1、串類型的定義、串類型的定義2、串的表示和實現(xiàn)、串的表示和實現(xiàn)3、串的模式匹配算法、串的模式匹配算法4、串操作應(yīng)用舉例、串操作應(yīng)用舉例目錄目錄第第四四章章 串串2 物料管理STRG2Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法1、串的定長順序存儲表示、串的定長順序存儲表示define MAXSTRLEN 255 / 最大串長最大串長Typedef unsignedchar Sstring MAXSTRLEN + 1 ； / 可

2、用可用 0 號單元存放串長度號單元存放串長度模式模式 P（樣品、子串）：要尋找的字符串，樣品、子串）：要尋找的字符串， 存于存于T1 至至 T M之中；之中；主串：在其中尋找模式的主字符串，主串：在其中尋找模式的主字符串， 存于存于S1 至至 S N之中；之中；問題：在主串中尋找一個模式？如何做，更快？問題：在主串中尋找一個模式？如何做，更快？ 采用最笨的辦法，一旦發(fā)現(xiàn)出現(xiàn)字符不匹配，則整個模式相對于原來的位置右移一位。采用最笨的辦法，一旦發(fā)現(xiàn)出現(xiàn)字符不匹配，則整個模式相對于原來的位置右移一位。 如下圖所示：如下圖所示：Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2 Pj-1

3、 Pj 失配位置失配位置 P1 P2 Pj-1 Pj 下次匹配位置下次匹配位置e.g: S=a b c a b c a b c d P= a b c a b c d a b c a b c d 模式右移一位模式右移一位3 物料管理STRG3Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法2、最原始的模式匹配程序：、最原始的模式匹配程序：Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2 Pj-1 Pj 失配位置失配位置 P1 P2 Pj-1 Pj 下次匹配位置下次匹配位置int Index( SString S,

4、SString T, int pos ) / 在主串S的第POS個字符之后，尋找模式T的匹配位置 i = pos ; j = 1; while ( i = S0 & j T0 ) return i-T0 / T在S中的匹配起始位置 else return 0; / Index4 物料管理STRG4Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法）起因：降低時間代價，從最壞情況下的起因：降低時間代價，從最壞情況下的 O（ n * m）降

5、低到降低到 O（n +m）；）； 此處此處 n 是主串的字符個數(shù)、是主串的字符個數(shù)、m 是子串的字符個數(shù)。是子串的字符個數(shù)。歷史：歷史：70 年年S.A.cook 從理論上證明可在從理論上證明可在 O（n +m）內(nèi)完成，以后由以內(nèi)完成，以后由以 上三人給出實現(xiàn)的程序。上三人給出實現(xiàn)的程序。E.g：說明最壞情況下時間復(fù)雜性的說明最壞情況下時間復(fù)雜性的 O（ n * m）的實例。的實例。 每比較每比較m = 3 次，移動模式一次。最后在主串的次，移動模式一次。最后在主串的 n-m+1 找到主串，比較找到主串，比較 （n-m+1）* m 次次 S=aaaaaaaaab P=aab a、b不等不等模模

6、式右移一位式右移一位 S=aaaaaaaaab P= aab a、b不等不等模模式右移一位式右移一位 S=aaaaaaaaab P= aab a、b不等不等模模式右移一位式右移一位 S=aaaaaaaaab P= aab a、b不等不等模模式右移一位式右移一位 S=aaaaaaaaab P= aab S=aaaaaaaaab P= aab S=aaaaaaaaab P= aab S=aaaaaaaaab P= aab a、b不等不等模模式右移一位式右移一位a、b不等不等模模式右移一位式右移一位a、b不等不等模模式右移一位式右移一位 完全匹配 n-m+1匹配起始位置匹配起始位置5 物料管理STR

7、G5Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） 說明說明 KMP 算法的實例：算法的實例：e.g: S = abcabcabcd P = abcabcd S = abcabcabcd P = abcabcd S = abcabcabcd P = abcabcd S = abcabcabcd P = abcabcd 失配點失配點右移一位，仍失配右移一位，仍失配又右移一位，仍失配又右移一位，仍失配再右移一位，三次比較之再右移一位，三次比較

8、之后，再進(jìn)行斷點處的比較后，再進(jìn)行斷點處的比較，比較上了！，比較上了！問題問題: 能否省去上述五次比較，直接能否省去上述五次比較，直接 進(jìn)行進(jìn)行 S7 和和 P4 之間的比較呢？之間的比較呢？本次比較省去！本次比較省去！本次比較省去！本次比較省去！三次比較省去！三次比較省去！6 物料管理STRG6Programing and Data Structures: Stringij3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） 說明說明 KMP 算法的實例：算法的實例：e.g: S = abcabcabcd P = a

9、bcabcd S = abcabcabcd P = abcabcd 失配點失配點省去上述五次比較，直接進(jìn)行省去上述五次比較，直接進(jìn)行 Si 和和 Pj (即即S7同同P4)之間的比較的可能性。之間的比較的可能性。直接尋找新的匹配位置ij Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2 Pj-1 Pj 失配點失配點 分析：當(dāng)分析：當(dāng) Si 和和 Pj 發(fā)生失配時，發(fā)生失配時， Si-j+1 Si-j+2 Si-1 P1 P2 Pj-1 Si-j+1 Si-k+1 Si-1 Si Si+1 P1 Pk-1 Pk 失配點失配點如果：如果： P1P2Pk-1 = Pj-k+1 Pj-

10、k+2 Pj-1；可以直接比較可以直接比較 前綴（長度前綴（長度k-1）= 以失配點的前一字符為結(jié)束位置的一串字符以失配點的前一字符為結(jié)束位置的一串字符7 物料管理STRG7Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） 分析：多個前綴時，會出現(xiàn)什么問題呢？分析：多個前綴時，會出現(xiàn)什么問題呢？ e.g：S = aaaaabaab P = aaaabij前綴：前綴：P1P2P3P4 = aaaa P1P2P3 = aaa P1P2 = aa

11、 P1 = a 1、如果，取前綴長度、如果，取前綴長度 k-1 = j -1 ( 4 )，則則 Si = Pk 即即 Pj 進(jìn)行比較，白做。故進(jìn)行比較，白做。故 前綴長度前綴長度 不可以為不可以為 j - 1 。 2、如果，取前綴長度、如果，取前綴長度 k-1 = 1 或或 2 ，即前綴分別為，即前綴分別為 P1=a 或或 P1P2=aa 則正確的位置則正確的位置 會漏過去，不行。故：前綴長度太短也不行。會漏過去，不行。故：前綴長度太短也不行。jS = aaaaabaabP = aaaabijiS = aaaaabaabP = aaaab 3、因此應(yīng)選前綴長度、因此應(yīng)選前綴長度 k -1 j-

12、1 （此例為此例為 k - 1 = 3）的最長的前綴。的最長的前綴。8 物料管理STRG8Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） NEXTj 的定義：當(dāng)失配點發(fā)生在的定義：當(dāng)失配點發(fā)生在 Pj 處時，主串中的失配點將和模式中的哪一個字符進(jìn)處時，主串中的失配點將和模式中的哪一個字符進(jìn) 行比較。那一個字符的位置定義為行比較。那一個字符的位置定義為 NEXTj。ij=1S = abcabaP = abai0 如果如果 j =1 ，意味著

13、失配點意味著失配點 Si != P1， 下一次下一次 Si+1 =?= P1MAX k 1 k j 且且 P1 Pk-1 = Pj-k+1Pj-1 1NEXTj = 解釋；解釋；1、 j=1iS = abcabaP = aba 解釋；解釋；2、 k -1 = 1 ，所以所以: 1 k j Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2Pj-k+1 Pj-1 Pj P1 Pk-1Pk 解釋；解釋；3、 否則否則 Si =?= P1S = abcabaP = abaij=1iS = abcabaP = abaj=19 物料管理STRG9Programing and Data St

14、ructures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） 求求 NEXTj 的實例：的實例：0 如果如果 j =1 ，意味著失配點意味著失配點 Si != P1， 下一次下一次 Si+1 =?= P1MAX k 1 k j 且且 P1 Pk-1 = Pj-k+1Pj-1 1NEXTj = Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2Pj-k+1 Pj-1 Pj P1 Pk-1Pk 求求 NEXTj ： e.g: j =1234567j = 12345678j = 1234

15、567 abcabcd abaabcac aaaaaaa NEXTj= 0111234 01122312 0123456 NEXTVALj= 0110114 01021302 000000010 物料管理STRG10Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2 Pj-1 Pj P1 Pk int Index_KMP( SString S, SString T, int pos ) / 在主串S的第POS個字符之后，尋找模式T的匹配位置 / 已知 NEXT 函數(shù)值

16、，T 非空，1=pos=Strlength(S) i = pos ; j = 1; while ( i = S0 & j T0 ) return i-T0 / T在S中的匹配起始位置 else return 0; / Index_KMP3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） 利用利用 NEXTj 函數(shù)值尋找模式的程序函數(shù)值尋找模式的程序：11 物料管理STRG11Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式

17、匹配算法（KMP 算法）算法） NEXTj 函數(shù)值的求法函數(shù)值的求法：1、由定義，、由定義，next1 = 02、若若nexti = j ，求求 nexti+1 = ? 由已知可得：由已知可得： P1P2 Pj-1= Pi-j+1Pi-j+2Pi-1 、若若 Pj = Pi ；則則 P1P2 Pj-1 Pj=Pi-j+1Pi-j+2Pi-1 Pi 所以，所以， nexti+1 = j +1 、若若 Pj != Pi ；不得認(rèn)為不得認(rèn)為 nexti+1 = 1 ；參見下述例子：參見下述例子： P=abcabdabcabcwabcabdabcabdx 6 12?nexti=12且且ii+1 求求

18、nexti+1 雖然雖然 P12 != Pj ，但但P1P2 P5= Pj-5Pj-4Pj-1 推出：推出： P1P2 P5P6= Pi-5Pi-4Pi-1 Pi 由此可以推出：由此可以推出： nexti+1=7Void get_next ( SString T, int & next ) i =1 ; next1 = 0 ; j= 0 ; while ( i T0 ) if ( j = 0 Ti = Tj ) +i ; +j ; nexti = j; else j = next j ; / get_next P=abcabdabcabcwabcabdabcabdx i=1i i+1

19、注意：注意：i 是模式的指針。指針是模式的指針。指針 j 為前綴個數(shù)為前綴個數(shù) + 112 物料管理STRG12Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） KMP 算法的時間復(fù)雜性：算法的時間復(fù)雜性：O（n+m）n:主串長度，主串長度，m:模式長度模式長度?？疾炖樱嚎疾炖樱?Sabcabcabcdabcdef Pabcabd1、從從 S 的指針觀察，的指針觀察， Ii 每右移一次，對應(yīng)一次比較。因每右移一次，對應(yīng)一次比較。因 此，

20、最多對應(yīng)著此，最多對應(yīng)著 n 次比較。次比較。2、從模式、從模式 P 進(jìn)行考察，當(dāng)失配時，進(jìn)行考察，當(dāng)失配時，j = nextj。主串失配主串失配 點點 Si 又將和又將和 Pj 進(jìn)行比較，對應(yīng)著新增加的比較次數(shù)。進(jìn)行比較，對應(yīng)著新增加的比較次數(shù)。 P 相對原來的位置右移。右移位數(shù)最多相對原來的位置右移。右移位數(shù)最多 n 次，新增加的次，新增加的 比較次數(shù)最多為比較次數(shù)最多為 n 次。次。所以，最多的比較次數(shù)最多為所以，最多的比較次數(shù)最多為 2n 次，同理生成次，同理生成 next 函函 數(shù)值的代價也不會大于數(shù)值的代價也不會大于 2m 。所以，總的代價所以，總的代價2(n+m)i13 物料管理

21、STRG13Programing and Data Structures: Stringii3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） KMP 算法的不用回溯的優(yōu)點：算法的不用回溯的優(yōu)點：考察例子：考察例子：Sabcabcabcdabcabd Pabcabd回溯：回溯：SabcabcabcdabcabdP abcabdi不回溯：不回溯：SabcabcabcdabcabdP abcabd12存放模式以存放模式以及模式的及模式的 next 值值存放主串的存放主串的每個扇區(qū)，每個扇區(qū)，一次存放一次存放 256 個字節(jié)個字節(jié)內(nèi)存內(nèi)存資料存于盤上資料存于盤上每個扇區(qū)每個扇區(qū) 256 個個字節(jié)字節(jié)模式模式 257 個字節(jié)個字節(jié)模式的前模式的前256 個個字節(jié)匹配