數(shù)據(jù)結(jié)構(gòu) 4串

1、1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容2第第4章章 串（串（String）4.2 4.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn)4.3 4.3 串的模式匹配算法串的模式匹配算法1. 定義定義2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)3. 存儲結(jié)構(gòu)存儲結(jié)構(gòu)4. 運(yùn)算規(guī)則運(yùn)算規(guī)則5. 實(shí)現(xiàn)方式實(shí)現(xiàn)方式4.1 4.1 串類型的定義串類型的定義3記為：記為： s = a1 , a2 , . , an (n0 ) 串名串名串值（用串值（用 括起來）括起來）串中字符個數(shù)（串中字符個數(shù)（n0n0）. n=0 . n=0 時稱為空串時稱為空串 。由一個或多個空格符組成的串。由一個或多個空格符組成的串。串串s s中任意個連續(xù)的字符序列叫中任

2、意個連續(xù)的字符序列叫s s的子串的子串; S; S叫叫主串主串。子串的第一個字符的序號。子串的第一個字符的序號。字符在串中的序號。字符在串中的序號。串長度相等，且對應(yīng)位置上字符相等。串長度相等，且對應(yīng)位置上字符相等。 串串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。元素為單個字符的特殊線性表。4.1 4.1 串類型的定義串類型的定義若干術(shù)語：若干術(shù)語： 串長：串長： 空白串：空白串： 子串：子串：子串位置：子串位置：字符位置：字符位置： 串相等：串相等：隱含結(jié)束符隱含結(jié)束符/0 ，即即ASCII碼碼NUL4練練

3、1：串是由串是由 字符組成的序列，一般記字符組成的序列，一般記為為 。練練2：現(xiàn)有以下現(xiàn)有以下4個字符串：個字符串：a =BEI b =JING c = BEIJING d = BEI JING問：問： 他們各自的長度？他們各自的長度？ a是哪個串的子串？在主串中的位置是多少？是哪個串的子串？在主串中的位置是多少？a =3，b =4，c = 7，d=8a是是c和和d的子串，在的子串，在c和和d中的位置都是中的位置都是1練練3：空串和空白串有無區(qū)別？空串和空白串有無區(qū)別？答：答：有區(qū)別?？沾袇^(qū)別?？沾?Null String)(Null String)是指長度為零的串；而空白是指長度為零的串；

4、而空白串串(Blank String),(Blank String),是指包含一個或多個空白字符是指包含一個或多個空白字符 ( (空空格鍵格鍵) )的字符串的字符串. .0個或多個個或多個S=a1a2an5ADT StringObjects: D=ai | aiCharacterSet, i=1, 2,，n, n0Relations: R1= | ai-1,ai D, i=2, ，nfunctions: / 有有1313種之多種之多StrAssign(&T, chars) / 串賦值，生成值為串賦值，生成值為charschars的串的串T TStrCompare(S,T) / 串比較，若串比較

5、，若STST，返回值大于，返回值大于0 0 StrLength(S) / 求串長，即返回求串長，即返回S S的元素個數(shù)的元素個數(shù) Concat(&T, S1, S2) / 串連接，用串連接，用T T返回返回S1S1S2S2的新串的新串SubString(&Sub, S, pos, len) / 求求S S中中pospos起長度為起長度為lenlen的子串的子串Index(S, T, pos) / 返回子串返回子串T T在在pospos之后的位置之后的位置 Replace(&S, T,V) / 用子串用子串V V替換子串替換子串T TADT String串的抽象數(shù)據(jù)類型定義（串的抽象數(shù)據(jù)類型定義

6、（參見教材參見教材P71）最最小小操操作作子子集集6 設(shè)設(shè) s =I AM A STUDENT, t =GOOD, q=WORKER。求：。求：練習(xí)：練習(xí)： StrLength(s) StrLength(t) SubString(s, 8, 7)= SubString(t, 2, 1)= Index(s, A)= Index(s, t)=Replace(s, STUDENT,q)=144STUDENTO30 （ s中沒有中沒有t！）?。㊣ AM A WORKER再問：再問：Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) ？ 見本章自測題，或

7、見嚴(yán)題集見本章自測題，或見嚴(yán)題集4.3 74.2串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn) 定長順序存儲表示定長順序存儲表示用一組地址連續(xù)的存儲單元存儲串值的字用一組地址連續(xù)的存儲單元存儲串值的字符序列符序列 堆分配存儲表示堆分配存儲表示用一組地址連續(xù)的存儲單元存儲串值的字用一組地址連續(xù)的存儲單元存儲串值的字符序列符序列, ,但存儲空間是在程序執(zhí)行過程中動態(tài)但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。分配而得。 串的塊鏈存儲表示串的塊鏈存儲表示鏈?zhǔn)椒绞酱鎯︽準(zhǔn)椒绞酱鎯Υ腥N機(jī)內(nèi)表示方法：串有三種機(jī)內(nèi)表示方法：順序順序存儲存儲鏈?zhǔn)芥準(zhǔn)酱鎯Υ鎯?A B C I NULLhead8定長順序存儲特點(diǎn)：定長順序存儲特

8、點(diǎn)：用一組連續(xù)的存儲單元來存放串，用一組連續(xù)的存儲單元來存放串，直接使用定長的字符數(shù)組來定義，數(shù)組的直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出上界預(yù)先給出，故稱為靜態(tài)存儲分配。故稱為靜態(tài)存儲分配。例如：例如：#define Maxstrlen 255 /用戶可用的最大串長用戶可用的最大串長 typedef unsigned char SString Maxstrlen1 ; SString s; /s是一個可容納是一個可容納255個字符的順序串。個字符的順序串。注：注：一般用一般用SString0來存放串長信息；來存放串長信息；C語言約定在串尾加結(jié)束符語言約定在串尾加結(jié)束符 0，以利操作

9、加速，但不計(jì)入串長；，以利操作加速，但不計(jì)入串長；若字符串超過若字符串超過Maxstrlen 則自動截?cái)啵ㄒ驗(yàn)殪o態(tài)數(shù)組存不則自動截?cái)啵ㄒ驗(yàn)殪o態(tài)數(shù)組存不 進(jìn)去）。進(jìn)去）。 討論：討論：想存放想存放超長超長字符串怎么辦？字符串怎么辦？靜態(tài)數(shù)組有缺陷！靜態(tài)數(shù)組有缺陷！實(shí)現(xiàn)方式：實(shí)現(xiàn)方式：參見教材參見教材P73編程兩例，兩串連接和編程兩例，兩串連接和求子串求子串改用改用動態(tài)動態(tài)分配的一維數(shù)組分配的一維數(shù)組“堆堆”！9例：例：順序存儲方式下獲得子串的函數(shù)順序存儲方式下獲得子串的函數(shù)SubString(&Sub, S, pos, len) Status SubString(SString &Sub, SS

10、tring S, int pos, int len ) if(posS0 | lenS0-pos+1) return ERROR; /pos不合法則告警不合法則告警 Sub1.len=Spos.pos+len-1; Sub0=len; return OK;P74P74將串將串S S中從第中從第pospos個字符開始長度為個字符開始長度為lenlen的字符序的字符序列復(fù)制到串列復(fù)制到串SubSub中中（注：串（注：串SubSub的預(yù)留長度與的預(yù)留長度與S S一樣）一樣）S = a1 , a2 , . , ann串長串長poslen10思路：思路：利用利用mallocmalloc函數(shù)合理預(yù)設(shè)串長空

11、間。函數(shù)合理預(yù)設(shè)串長空間。特點(diǎn)：特點(diǎn)： 若在操作中串值改變，還可以利用若在操作中串值改變，還可以利用reallocrealloc函數(shù)按新串函數(shù)按新串長度長度增加增加( (堆砌堆砌) )空間?？臻g。typedef struct char *ch; / 若非空串,按串長分配空間; 否則 ch = NULLint length; /串長度HString堆分配存儲特點(diǎn)：堆分配存儲特點(diǎn)：仍用一組連續(xù)的存儲單元來存放串，仍用一組連續(xù)的存儲單元來存放串，但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。約定：約定：所有按堆存儲的串，其關(guān)鍵信息放置在：所有按堆存儲的串，其關(guān)鍵

12、信息放置在：11Status StrInsert ( HString &S, int pos, HString T ) /在串在串S的第的第pos個字符之前（包括尾部）插入串個字符之前（包括尾部）插入串Tif (posS.length+1) return ERROR; /pos不合法則告警不合法則告警 if(T.length) /只要串只要串T不空，就需要重新分配不空，就需要重新分配S空間，以便插入空間，以便插入T if (!（S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char) ) exit(OVERFLOW); for ( i

13、=S.length-1; i=pos-1; -i ) /為插入為插入T而騰出而騰出pos之后的位置之后的位置 S.chi+T.length = S.chi; /從從S的的pos位置起全部字符均后移位置起全部字符均后移 S.chpos-1pos+T.length-2 = T.ch0T.length-1; /插入插入T，略，略/0 S.length + = T.length; /刷新刷新S串長度串長度return OK;/StrInsert例：例：用用“堆堆”實(shí)現(xiàn)串插入操作實(shí)現(xiàn)串插入操作(教材教材P75) 121 Status StrAssign(HString &T, char *chars)2

14、 if (T.ch) free(T.ch);3 for (i=0, c=chars; c; +i, +c); /求串長度求串長度i4 if (!i) T.ch = NULL; T.length = 0; /串長串長i為為0，即空串，即空串5 else6 if (!(T.ch = (char*)malloc(i*sizeof(char)7 exit(OVERFLOW);8 T.ch0.i-1 = chars0.i-1;9 T.length =i;10 11 return OK;/StrAssign指針變量指針變量c也可以自增！也可以自增！意即每次后移一個數(shù)據(jù)意即每次后移一個數(shù)據(jù)單元。單元。附：堆

15、分配存儲表示附：堆分配存儲表示直到終值為直到終值為“假假”停止，串尾特征是停止，串尾特征是/0NULL=013討論：討論：法法1 1存儲密度為存儲密度為 ；法；法2 2存儲密度為存儲密度為 ；顯然，若顯然，若數(shù)據(jù)元素很多，用法數(shù)據(jù)元素很多，用法2 2存儲更優(yōu)存儲更優(yōu)稱為稱為塊鏈結(jié)構(gòu)塊鏈結(jié)構(gòu)鏈?zhǔn)酱鎯μ攸c(diǎn)鏈?zhǔn)酱鎯μ攸c(diǎn) ：用鏈表存儲串值，易插入和刪除。用鏈表存儲串值，易插入和刪除。法法1 1：鏈表結(jié)點(diǎn)（數(shù)據(jù)域）大小取鏈表結(jié)點(diǎn)（數(shù)據(jù)域）大小取1 1法法2 2：鏈表結(jié)點(diǎn)（數(shù)據(jù)域）大小取鏈表結(jié)點(diǎn)（數(shù)據(jù)域）大小取n(n(例如例如n=4)n=4)9/189/189/15=3/59/15=3/5 A B C I

16、 NULLheadheadA B C D E F G H I # # # NULL14#define CHUNKSIZE 80 /可由用戶定義的塊大小可由用戶定義的塊大小typedef struct Chunk /首先定義結(jié)點(diǎn)類型首先定義結(jié)點(diǎn)類型 char ch CHUNKSIZE ; /結(jié)點(diǎn)中的數(shù)據(jù)域結(jié)點(diǎn)中的數(shù)據(jù)域 struct Chunk * next ; /結(jié)點(diǎn)中的指針域結(jié)點(diǎn)中的指針域Chunk; 塊鏈類型定義：塊鏈類型定義：typedef struct /其次定義用鏈?zhǔn)酱鎯Φ拇愋推浯味x用鏈?zhǔn)酱鎯Φ拇愋?Chunk *head; /頭指針頭指針 Chunk *tail; /尾指針尾

17、指針 int curLen; /結(jié)點(diǎn)個數(shù)結(jié)點(diǎn)個數(shù) Lstring; /串類型只用一次，前面可以不加串類型只用一次，前面可以不加Lstring15再次強(qiáng)調(diào)：再次強(qiáng)調(diào)：串與線性表的運(yùn)算有所不同，是以串與線性表的運(yùn)算有所不同，是以“串的整體串的整體”作作為操作對象，例如查找某子串，在主串某位置上插入一個子串為操作對象，例如查找某子串，在主串某位置上插入一個子串等。等。算法目的：算法目的：確定主串中所含子串第一次出現(xiàn)的位置確定主串中所含子串第一次出現(xiàn)的位置（定位定位） 即如何實(shí)現(xiàn)即如何實(shí)現(xiàn) Index(S,T,pos)函數(shù)函數(shù)（見教材（見教材P79）4.3 串的模式匹配算法串的模式匹配算法模式匹配模式

18、匹配(Pattern Matching) (Pattern Matching) 即即子串定位運(yùn)算子串定位運(yùn)算。初始條件：初始條件：串串S S和和T T存在，存在，T T是非空串，是非空串，1posStrLength(s)1posStrLength(s)操作結(jié)果：操作結(jié)果：若主串若主串S S中存在和串中存在和串T T值相同的子串，則返回它在主值相同的子串，則返回它在主串串S S中第中第pospos個字符之后個字符之后第一次第一次出現(xiàn)的位置；否則函數(shù)值為出現(xiàn)的位置；否則函數(shù)值為0 0。注：注：S S稱為稱為被匹配的串被匹配的串，T T稱為稱為模式串模式串。若。若S S包含串包含串T T，則稱，則稱

19、“匹配成功匹配成功”。否則稱。否則稱 “匹配不成功匹配不成功” 。S=a b a b c a b c a c b a bT=T=a b c a cpos=516 BF算法設(shè)計(jì)思想算法設(shè)計(jì)思想（見教材（見教材P79） 將主串的第將主串的第pospos個字符和模式的第個字符和模式的第1 1個字符比較，個字符比較， 若若相等相等，繼續(xù)逐個比較后續(xù)字符；，繼續(xù)逐個比較后續(xù)字符； 若若不等不等，從主串的下一字符（，從主串的下一字符（pos+1pos+1）起，重新與第一個）起，重新與第一個字符比較。字符比較。 BF算法算法 （又稱古典或經(jīng)典的、樸素的、窮舉的）（又稱古典或經(jīng)典的、樸素的、窮舉的） KMP算

20、法算法（特點(diǎn)：速度快）（特點(diǎn)：速度快）算法算法種類：種類： 直到主串的一個連續(xù)子串字符序列與模式相等直到主串的一個連續(xù)子串字符序列與模式相等 。返回值。返回值為為S S中與中與T T匹配的子序列匹配的子序列第一個字符的序號第一個字符的序號，即匹配成功。，即匹配成功。否則，匹配失敗，返回值否則，匹配失敗，返回值 0 .0 .返回5S=a b a b c a b c a c b a bT=T=a b c a cIndex(S, T, 1)171 int Index(SString S, SString T, int pos) 2 i=pos; j=1;3 while ( i=S0 & jT0) r

21、eturn i-T0; /子串結(jié)束，說明匹配成功子串結(jié)束，說明匹配成功8 else return 0;9 /Index BFBF算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)即即Index（）操作的實(shí)現(xiàn)（）操作的實(shí)現(xiàn) （見教材（見教材P79） 0號單元存放串的長度，號單元存放串的長度，P73匹配成功時匹配成功時i指向的與子串最后一個字符相等的字指向的與子串最后一個字符相等的字符符18BF算法：算法：int Index(S, T,1)i=1;j=1;while(i=s0 &jT0) return i-T0; else return 0;BFBF算法在最壞的情況下需要比較字算法在最壞的情況下需要比較字符的總次數(shù)為符的總次數(shù)

22、為(n-m+1)*mO(n*m)最糟糕的情況：最糟糕的情況：主串前面主串前面n-mn-m個位置個位置都都部分匹配部分匹配到子串的最后一位，即到子串的最后一位，即這這n-mn-m位比較了位比較了m m次，別忘了最后次，別忘了最后m m位位也各比較了一次，還要加上也各比較了一次，還要加上m m！BFBF算法的最壞時間復(fù)雜度算法的最壞時間復(fù)雜度但一般情況下但一般情況下BFBF算法的時間復(fù)算法的時間復(fù)雜度為雜度為O(n+m)BF算法的效率分析討論：討論：令令n n為主串長度，為主串長度，m m為子串長為子串長度。匹配最糟糕的情況是什么？度。匹配最糟糕的情況是什么？19KMP算法算法（特點(diǎn)：速度快）（特

23、點(diǎn)：速度快） KMPKMP算法設(shè)計(jì)思想算法設(shè)計(jì)思想 KMP算法的推導(dǎo)過程算法的推導(dǎo)過程 KMPKMP算法的實(shí)現(xiàn)算法的實(shí)現(xiàn) （關(guān)鍵技術(shù)（關(guān)鍵技術(shù): :計(jì)算計(jì)算nextjnextj） KMPKMP算法的算法的時間復(fù)雜度時間復(fù)雜度D. E. Knuth, V. R. Pratt, J. H. Morris20能否利用已經(jīng)能否利用已經(jīng)部分匹配部分匹配的結(jié)果而加快模式串的滑動速度？的結(jié)果而加快模式串的滑動速度？能！能！而且主串而且主串S S的指針的指針i i不必回溯不必回溯！可提速到！可提速到O(n+m)O(n+m)！例：例： KMP KMP算法設(shè)計(jì)思想：算法設(shè)計(jì)思想： ( (參見教材參見教材P80-8

24、4P80-84）S=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cIndex_kmpIndex_kmp的返回值應(yīng)為的返回值應(yīng)為i=6i=6需要討論兩個問題：需要討論兩個問題： 如何如何“記憶記憶”部分匹配結(jié)果？部分匹配結(jié)果？ 如何由如何由“記憶記憶”結(jié)果計(jì)算出主串結(jié)果計(jì)算出主串S S第第i i個字符應(yīng)該與模式個字符應(yīng)該與模式T T中中哪個字符再比較？即確定模式哪個字符再比較？即確定模式T T中的新比較起點(diǎn)中

25、的新比較起點(diǎn)k k. .i ii ii ik kk k a b aa b c演示程序演示程序21第一步，先第一步，先把模式把模式T所有可能的失配點(diǎn)所有可能的失配點(diǎn)j所對應(yīng)的所對應(yīng)的nextj計(jì)算出來計(jì)算出來；第二步：執(zhí)行定位函數(shù)第二步：執(zhí)行定位函數(shù)Index_KMP （與（與BF算法模塊非常相似）算法模塊非常相似） KMPKMP算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)即即Index( )操作的實(shí)現(xiàn)操作的實(shí)現(xiàn) （見教材（見教材P82） 1 int Index_KMP(SString S, SString T, int pos) 2 i=pos; j=1;3 while ( i=S0 & jT0) return i-

26、T0; /子串結(jié)束，說明匹配成功子串結(jié)束，說明匹配成功8 else return 0;9 /Index_KMP22 KMP算法的推導(dǎo)過程：算法的推導(dǎo)過程：（見教材（見教材P81）抓住部分匹配結(jié)果的兩個特征：抓住部分匹配結(jié)果的兩個特征：兩式聯(lián)立可得：兩式聯(lián)立可得：T1Tk-1=Tj-(k-1)j-(k-1) Tj-1注意：注意：j 為當(dāng)前已知的失配位置，我們的目標(biāo)是計(jì)算新起點(diǎn)為當(dāng)前已知的失配位置，我們的目標(biāo)是計(jì)算新起點(diǎn) k，僅剩一個未知數(shù)僅剩一個未知數(shù)k，理論上已可解，且，理論上已可解，且k僅與模式串僅與模式串T有關(guān)！有關(guān)！ 則則S S的的i-(k-1)i-(k-1)i-1i-1位位T T的的j

27、-(k-1)j-(k-1)j-1j-1位位 即即(4-3(4-3）式含義）式含義S=a b a b c a b c a c b a bT=T=a b c a ci ik k則則T T的的1 1k-1k-1位位S S的的i-(k-1)i-(k-1)i-1i-1位位 即即(4-2(4-2）式含義）式含義i ik kj jS=a b a b c a b c a c b a bT=T=a b c a c剛才肯定是在剛才肯定是在S的的i處和處和T的第的第j字符字符 處失配處失配設(shè)目前應(yīng)與設(shè)目前應(yīng)與T的第的第k字符開始比較字符開始比較23 KMP算法的推導(dǎo)過程算法的推導(dǎo)過程(續(xù)）續(xù)）：根據(jù)模式串根據(jù)模式串

28、T的規(guī)律：的規(guī)律： T1Tk-1=Tj-(k-1)j-(k-1) Tj-1和已知的當(dāng)前失配位置和已知的當(dāng)前失配位置j ，可以歸納出計(jì)算新起點(diǎn)，可以歸納出計(jì)算新起點(diǎn) k的表達(dá)式。的表達(dá)式。令令k = next j ，則則next j 0 當(dāng)當(dāng)j1時時max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其他情況其他情況討論：討論： next j 有何意義？有何意義？ 一旦失配，應(yīng)從模式串一旦失配，應(yīng)從模式串T中第中第next j 個字符開始與個字符開始與S的失配的失配點(diǎn)點(diǎn)i 重新匹配重新匹配! next j 怎么求？怎么求？ 后面會舉例后面會舉例（參見教材（參見教

29、材P81）例：例： 模模 式式 串串 T： a b a a b c a c 可能失配位可能失配位 j： 1 2 3 4 5 6 7 8新匹配位新匹配位 nextj :next j 0 當(dāng)當(dāng)j1時時max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其他情況其他情況0 1 1 2 2 3 1 2討論：討論：j=1時時, next j 0；因?yàn)閷儆谝驗(yàn)閷儆凇癹=1”;j=2時時, next j 1；因?yàn)閷儆谝驗(yàn)閷儆凇捌渌闆r其他情況”；剛才已歸納：剛才已歸納：j=3時時, k=2，只需查看，只需查看T1=T2 2。因不等，故。因不等，故“其他情其他情況況”；j=4

30、時時, k=2，3，要查看，要查看T1=T3 3 和和T1T2=T2 2 T3 3 j=5時時, k=2，3，4，要查看，要查看T1=T4 4 、T1T2=T3 3T4 和和 T1T2T3 3=T2 2T3 3T4以此類推，可得后續(xù)以此類推，可得后續(xù)nextj值。值。25討論：討論： next j 有何物理意義？有何物理意義？nextjnextj函數(shù)表征著模式中兩段字符之間相匹配的最大子函數(shù)表征著模式中兩段字符之間相匹配的最大子串的長度（除串本身外）。串的長度（除串本身外）?？梢?，模式中可見，模式中相似部分越多，則相似部分越多，則nextjnextj函數(shù)越大函數(shù)越大，它既，它既表示表示模式模式

31、T字符之間的相關(guān)度越高，也表示字符之間的相關(guān)度越高，也表示j j位置以前與主串位置以前與主串部部分匹配分匹配的字符數(shù)越多。的字符數(shù)越多。即：即：nextjnextj越大，模式串向右滑動得越遠(yuǎn)，與主串進(jìn)行越大，模式串向右滑動得越遠(yuǎn)，與主串進(jìn)行比較的次數(shù)越少，時間復(fù)雜度就越低。比較的次數(shù)越少，時間復(fù)雜度就越低。next j max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 模式串從首位往右模式串從首位往右直到直到k-1k-1位位模式串從模式串從j j的前一位的前一位往左直到往左直到j(luò)-(k-1)j-(k-1)位位想一想：如果主串和模式均為二進(jìn)制碼流，用想一想：如果主

32、串和模式均為二進(jìn)制碼流，用KMPKMP算法算法效果如何？效果如何？26next函數(shù)的改進(jìn)算法函數(shù)的改進(jìn)算法前面定義的前面定義的next函數(shù)在某些情況下還是有缺陷函數(shù)在某些情況下還是有缺陷例如：模式例如：模式aaaab與主串與主串a(chǎn)aabaaaab匹配情況：匹配情況：模式：模式： a a a a bj：1 2 3 4 5 nextj： 0 1 2 3 4S: a a a b a a a a b T: a a a a b i: 1 2 3 4 5 6 7 8 9 a a a a ba a a a ba a a a ba a a a bnextvalj=nextvalk nextj=k且Tj=Tkn

33、extj其他nextvalj： 0 0 0 0 427討論兩個有關(guān)討論兩個有關(guān)next j 的問題：的問題： 怎樣簡捷計(jì)算怎樣簡捷計(jì)算nextj？ 可用遞推法編程實(shí)現(xiàn)！可用遞推法編程實(shí)現(xiàn)?。▍⒁姡▍⒁奝83簡捷算法）簡捷算法）計(jì)算計(jì)算nextj的時間為的時間為O(m)1 void get_next(SString T, int &next )2 /next函數(shù)值存入數(shù)組函數(shù)值存入數(shù)組next3 i=1; next1=0; j=0; /j是重復(fù)子串長是重復(fù)子串長4 while(iT0 )5 if(j= = 0|Ti= =Tj)+i;+j;nexti=j;6 else j=nextj;7 8/ g

34、et_next1 void get_nextval(SString T, int &nextval )2 /next函數(shù)修正值存入數(shù)組函數(shù)修正值存入數(shù)組nextval3 i=1; nextval1=0; j=0;4 while(iT0 )5 if(j= = 0|Ti= =Tj ) +i;+j;6 if(Ti!=Tj) nextvali=j;7 else nextvali=nextvalj; 8 else j=nextvalj; 9/ get_nextval next j 是否完美無缺？是否完美無缺？答：未必，例如當(dāng)答：未必，例如當(dāng)S=a b a a a a b,T=a a a a b時時仍有多余動作仍有多余動作（參見（參見P84改進(jìn)算法改進(jìn)算法, 稱為稱為nextval j ）28 KMPKMP算法的算法的時間復(fù)雜度時間復(fù)雜度 因?yàn)橛?jì)算因?yàn)橛?jì)算nextj的時間為的時間為O(m);且且Index_KMP函數(shù)（函數(shù)（沒有回