《數(shù)據(jù)結(jié)構(gòu)》串》PPT課件

1、第4章 串4.1串及其操作 4.2串的存儲(chǔ)結(jié)構(gòu)4.3串的基本運(yùn)算實(shí)現(xiàn) 4.4串的模式匹配運(yùn)算 習(xí)題 在非數(shù)值處理的應(yīng)用領(lǐng)域中，字符串的應(yīng)用非常廣泛。如編輯器(Edit、Word本質(zhì)上是字符串處理)、信息檢索(字符串比較)等。 實(shí)際上，編寫數(shù)值計(jì)算程序的機(jī)會(huì)很有限。從發(fā)明計(jì)算機(jī)的思路來說，其目的是為了模擬人類的對(duì)信息的邏輯處理方法，而數(shù)值計(jì)算僅僅是一種邏輯思路的標(biāo)準(zhǔn)化。 現(xiàn)今我們使用的計(jì)算機(jī)的硬件結(jié)構(gòu)主要反映數(shù)值計(jì)算的需要的，因此，在處理字符串?dāng)?shù)據(jù)時(shí)比處理整數(shù)和浮點(diǎn)數(shù)要復(fù)雜的多。而且，在不同類型的應(yīng)用中，所處理的字符串具有不同的特點(diǎn)，要有效地實(shí)現(xiàn)字符串的處理，就必須根據(jù)具體情況使用合適的存儲(chǔ)結(jié)構(gòu)

2、。下面將討論字符串的一些處理方法和字符串的幾種不同的存儲(chǔ)結(jié)構(gòu)。4.1 串及其操作 4.1.1 串的邏輯結(jié)構(gòu) 定義：串(字符串)，是由零個(gè)或多個(gè)字符組成的有限序列。一般記作： s=a0a1an-2an-1 (n0) s是串的名。 雙引號(hào)括起來是是串的值。 n為串的長度。 空串為零個(gè)字符，n=0。 子串為串中任意個(gè)連續(xù)的字符組成的子序列。 位置為字符在序列中的序號(hào)。為字符在串中的稱作。 子串位置以子串的第一個(gè)字符在主串中的位置來表示。舉例：a=This is a string 串長=16 b=string串長=6 ，是a的子串，在a串的位置是10 c= 串長=2，的空格串，它不是a和b的子串。 串

3、的集合定義： 設(shè)string=(D，R)是一個(gè)數(shù)據(jù)結(jié)構(gòu)，其中 D=a0，a1，an-1 為字符元素的集合，i=0，n-1 ，并且n0。 R=|ai-1，aiD，i=1，2，n-1 R為上元素的關(guān)系集合 則稱 string是一個(gè)字符串。字符串與線性表的區(qū)別是 它的數(shù)據(jù)對(duì)象為字符集。4.1.2 串的基本運(yùn)算 (1)賦值操作assign(s，t)。將t的值賦給s。 (2)串相等判斷equal(s，t)函數(shù)。若s串與t串相等，則函數(shù)返回1，否則函數(shù)將返回0。 (3)串的聯(lián)接操作concat(s，t)函數(shù)。將s串和t串聯(lián)接成一個(gè)串，新生成的串是s串在前，而t串緊接s串的尾部。 例如，設(shè)a=data ,

4、b=structure,執(zhí)行concat(a,b), 新生成的串是data structure。 串的聯(lián)接不滿足交換律:concat(s,t)!=concat(t,s) ; 串的聯(lián)接滿足結(jié)合律: concat(s1，concat(s2，s3)=concat(s1，s2，s3) 其運(yùn)算結(jié)果是將這3個(gè)串的值依次首尾相接得到一個(gè)新串。 (4)求長度length(s)函數(shù)。其函數(shù)值為串s中字符的個(gè)數(shù)。 (5)求子串sub(s，start，len，t)。若 0startlength(s) 0lenlength(s)-start則t中值為從串s中第start個(gè)字符起，長度為len的字符序列，并且函數(shù)返回值

5、為1；否則函數(shù)返回值為0。 例如，s=data structure, sub(s，5，5，t), 則 t=struc。 (6)子串定位index(s,t)函數(shù)。若在主串s中存在和t相等的子串，則函數(shù)值為s中第一個(gè)這樣的子串在主串s中的位置，否則函數(shù)值為-1。注意，在此t不能是個(gè)空串。例如，s=data structure， t=ru, 則index(s,t)=7。 (7)替換replace(s,t,v)。操作結(jié)果是以串v替換串s中出現(xiàn)的所有和非空子串t相同的不重疊子串。4.2 串的存儲(chǔ)結(jié)構(gòu) 在程序執(zhí)行的過程中，串的值可變。所以，與在程序出現(xiàn)的其他類型的變量一樣，給要處理的串賦一個(gè)變量名，這樣在

6、對(duì)串進(jìn)行操作時(shí)，可以通過變量名訪其值。 串的存儲(chǔ)結(jié)構(gòu)有兩種形式： 一種是將串設(shè)計(jì)成一種結(jié)構(gòu)類型，串是字符型的數(shù)組，從串名可直接訪問到串值，串值的存儲(chǔ)分配是在編譯時(shí)完成； 一種是串值的存儲(chǔ)分配是在程序運(yùn)行時(shí)完成，在串名和串值之間需要建立一個(gè)對(duì)照表，這個(gè)對(duì)照表稱之為串名的存儲(chǔ)映像。 4.2.1 順序存儲(chǔ)結(jié)構(gòu) 用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串字符序列。唯一確定一個(gè)串，需要二個(gè)數(shù)據(jù)：串的起始地址，串的長度。在C語言中，對(duì)字符串處理兩個(gè)要素是：數(shù)組名，結(jié)束標(biāo)記符號(hào)，如圖4.1所示 chdatastr ucture001234567891011121314n-1 圖4.1串的順序存儲(chǔ)結(jié)構(gòu) 說明：ch是一個(gè)數(shù)

7、組，存放串”data structure”，判斷串的結(jié)束標(biāo)志為字符0，在它前面的字符組成串。在這種表示方法中，訪問子串方便，但插入、刪除麻煩，需要大量移動(dòng)字符。例如，要取子串 sub(s,5,4,t)，只要將數(shù)組ch5到ch8賦給t，便可實(shí)現(xiàn)求子串運(yùn)算。 順序存儲(chǔ)結(jié)構(gòu)又分為非緊縮格式和緊縮格式。 a.非緊縮格式 一個(gè)存儲(chǔ)單元存放一個(gè)字符。若計(jì)算機(jī)的存儲(chǔ)單元是按字編址，并且計(jì)算機(jī)字長大于八位二進(jìn)制數(shù)，這樣，在一個(gè)存儲(chǔ)單元僅僅存放一個(gè)字符就浪費(fèi)存儲(chǔ)空間，但簡(jiǎn)化了對(duì)串的操作。例如，在一個(gè)字長為32位的計(jì)算機(jī)中，其一個(gè)存儲(chǔ)單元為四個(gè)字節(jié)，但只存放一個(gè)字符(字符只占一個(gè)字節(jié))，所以空間浪費(fèi)，如圖4.2所

8、示。 b.緊縮格式 圖4.3緊縮格式為了節(jié)省存儲(chǔ)空間，也可以用緊縮方式，即在一個(gè)存儲(chǔ)單元中存放多個(gè)字符，如圖4.3所示，在一個(gè)存儲(chǔ)單元中存放4個(gè)字符。顯然，緊縮格式可以節(jié)省空間，但在對(duì)串值進(jìn)行訪問時(shí)需要花費(fèi)較多時(shí)間分離同一存儲(chǔ)單元中字符。 2.緊縮格式d a t a s t ru c t ur e圖4.3緊縮格式da ta s t ruc tu re圖4 |2 非緊縮格式 d a t a s t ru c t ur e圖4.3緊縮格式 實(shí)際使用：如果計(jì)算機(jī)采用以字節(jié)為存儲(chǔ)單元，一個(gè)字符占用一個(gè)存儲(chǔ)單元(字節(jié) )，此時(shí)既節(jié)省空間，處理又方便，C語言中字符串存儲(chǔ)采用該方法，即圖4.1所示，在后面討

9、論的串運(yùn)算，都采用這種存儲(chǔ)結(jié)構(gòu)（字符數(shù)組）。 4.2.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 用鏈表方式存儲(chǔ)串值。由于串結(jié)構(gòu)的特殊性，即結(jié)構(gòu)中每一個(gè)數(shù)據(jù)元素是一個(gè)字符，用鏈表存儲(chǔ)串值時(shí)，結(jié)點(diǎn)的大小需要討論每個(gè)結(jié)點(diǎn)是存放一個(gè)字符，還是存放多個(gè)字符。例如，圖4.4所示是結(jié)點(diǎn)大小分別為存放4個(gè)字符和1個(gè)字符。(a)結(jié)點(diǎn)大小為4的鏈表 (b)結(jié)點(diǎn)大小為1的鏈表 圖4.4結(jié)點(diǎn)大小不同的鏈表 4.2.3 堆存儲(chǔ)結(jié)構(gòu) 堆結(jié)構(gòu)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。系統(tǒng)將一個(gè)容量很大的連續(xù)空間作為多個(gè)串值可共用的空間，每當(dāng)建立一個(gè)新串時(shí)，若該串尚未賦值，它不占堆的存儲(chǔ)空間；若要給該串賦值，首先，從未分配的堆空間中分配給該串值要求的空間，然后，將串值寫

10、入到分配的空間中；同樣，當(dāng)串的值無意義或串值被賦空串時(shí)，原串值所占用的空間要還給堆。所以，串的存儲(chǔ)地址是動(dòng)態(tài)分配的，一個(gè)串值的確定是通過串在堆中的起始位置和串的長度實(shí)現(xiàn)的。為此，串名和串值之間要建立一個(gè)對(duì)照表。例如圖4.5，所示為對(duì)照表和存放字符串的堆。 串名起址串長0123456789 A 0 4datastruct B 4 9urebookfree=17 C 13 4 (a)對(duì)照表 (b)堆store的狀態(tài) 圖4.5 堆存儲(chǔ)結(jié)構(gòu)在圖中假定，堆是一個(gè)字符數(shù)組，定義為： char storeMAX；/*存放串值的堆，MAX表示連續(xù)空間最大容量*/ int free；/* free為當(dāng)前可分配空

11、間起始地址的指針，起初值為0 */ 在堆中存放的三個(gè)串分別是： a=data b=structure c=book 4.3 串的基本運(yùn)算實(shí)現(xiàn) 字符串是一種特殊的線性表，對(duì)它的操作不同于對(duì)線性表的處理，有自己獨(dú)特的處理方法。在實(shí)際串的處理中，其存儲(chǔ)結(jié)構(gòu)為字符數(shù)組。下面討論在這種存儲(chǔ)方式下的串的運(yùn)算。 定義： #define MAX 100 /* MAX為數(shù)組最大下標(biāo) */ char tMAX, sMAX; /* s,t為存放字符串的數(shù)組 */ (1) 算法4.1 求字符串長度函數(shù)length(s) 。 int length(char s) /* 求串s的長度 */ int i; for (i=0

12、, si!=0；i+)； return(i)； (2)算法4.2求子串函數(shù)substr(s,start,len,t) int sub(char s,int start,int len,char t) /* 若0startlength(s)并且0lenlength(s)-start，則將串s中從第start個(gè)字符起，長度為len的字符序列復(fù)制到t中，函數(shù)返回1；否則函數(shù)返回0 */ int n,i; if(start=(n=length(s) return(0); if(lenn) return(0); for(i=0;i=MAX) return(0); for(i=0;in;i+) sm+i=

13、ti; ti=0; /* 聯(lián)接得到串的結(jié)束標(biāo)志 */ return(1); (4)算法4.4 串相等判斷函數(shù)equal(s,t) int equal(char s,char t) /* 若s串與t串相等，則函數(shù)返回1，否則函數(shù)將返回0 */ int m,n,i; m=length(s); n=length(t); if(m!=n) return(0); for(i=0;im;i+) if(si!=ti) return(0); return(1); 另外，在C語言的庫函數(shù)中已經(jīng)包含了一些串操作函數(shù)，例如，賦值函數(shù)strcpy，判斷函數(shù)strcmp，求長度函數(shù)strlen，求子串substr等，在

14、程序設(shè)計(jì)中可以直接調(diào)用。 4.4 串的模式匹配運(yùn)算 模式匹配：子串定位運(yùn)算index(s,t,start)，即在主串s中尋找子串t的過程通常稱作串的模式匹配(其中t稱為模式)。 當(dāng)匹配成功時(shí): index(s,t,start)函數(shù)的值為t在s中的序號(hào)； 當(dāng)匹配失敗時(shí)， index(s,t,start)函數(shù)的返回值為-1。 為增加通用性，定義了一個(gè)start用來表示在s中開始匹配的字符位置。例如， s=abcdef，t=cde index(s，t，0)=2 s=abcdef，t=ab index(s，t，0)=0 s=abcdef，t=ad index(s，t，0)=-1 4.4.1 BF算法(

15、Brute-Force) 算法的基本思想：在主串s中取從第i(i的初值為start)個(gè)字符起，并且長度和串t相等的子串和t比較，若相等，則求得函數(shù)值為i，否則i增1直至串s中不存在從i開始和t相等的子串為止，匹配失敗，返回-1。 例如，主串s為ababcabcacbab 模式串t為abcac 匹配過程如圖4.6所示 s=ababcabcacb ab取i=0開始子串subch!=ti=0t=abcac匹配失敗，i=i+1=1s=ababcabcacbab取i=1開始子串subch!=ti=1 t=abcac匹配失敗，i=i+1=2s=ababcabcacbab“取i=2開始子串subch!=ti

16、=2 t=abcac匹配失敗，i=i+1=3s=ababcabcacbab取i=3開始子串subch!=ti=3 t=abcac匹配失敗，i=i+1=4s=ababcabcacbab取i=4開始子串subch!=ti=4 t=“abcac匹配失敗，i=i+1=5s=ababcabcacbab取i=5開始子串subch=ti=5 t=abcac匹配成功，返回i=5 圖4.6 取子串的匹配過程 算法4.5 取子串進(jìn)行比較的模式匹配算法。 int index(char s,char t,int start) int i,eq,m,n; char subchMAX; m=strlen(s); n=st

17、rlen(t); if(startm) return(-1); /*起始點(diǎn)+模式串長度主串長度 */ /*subch為在s中從i開始與t相同長度子串*/ i=start; eq=sub(s,i,n,subch) ； while(eq) if(strcmp(t,subch) break; /* i開始的子串與t相等 */ else i+; eq=sub(s,i,n,subch); /*從i開始的子串與t不相等*/ if(eq) return(i); else return(-1); 有回溯的模式匹配算法：設(shè)置兩個(gè)指針i和j分別指向主串s和模式串t中當(dāng)前正待比較的字符位置。算法的基本思想是： 初始

18、 i=0；j=0; 做循環(huán) 若 si=tj 則 (繼續(xù)逐個(gè)比較后續(xù)字符i+,j+) 否則,從主串的第二個(gè)字符起在重新和模式串比較(i返回到原位置加1，j返回0) . 直至模式串t的每一個(gè)字符依次和主串s的一個(gè)連續(xù)的字符序列相等，則稱匹配成功，否則稱匹配失敗。 該算法與前面所討論的算法相同，只是前者是以每一個(gè)位置為始點(diǎn)，取出子串與t比較，而后是以每一個(gè)位置為出發(fā)點(diǎn)，與t比較，并且若匹配成功比較到t串結(jié)束，否則只需要比較到某一位置，即串s與串t的字符不相同。 i=2 s2!=t2 匹配失敗第一趟匹配s=ababcabcacbabi=0開始t=abcaci=i-j+1;j=0; 進(jìn)入下一趟 j=2

19、i=1 s1!=t0 匹配失敗第二趟匹配s=ababcabcacbabi=1開始t=abcaci=i-j+1;j=0; 進(jìn)入下一趟 j=0 i=6 s6!=t4 匹配失敗第三趟匹配s=ababcabcacbabi=2開始t=abcaci=i-j+1;j=0; 進(jìn)入下一趟 j=4 例如主串s為ababcabcacbab，模式串t為abcac，匹配過程如圖4.7所示 i=3 s3!=t0 匹配失敗第四趟匹配s=ababcabcacbabi=3開始t=abcaci=i-j+1;j=0; 進(jìn)入下一趟 j=0 i=4 s4!=t20 匹配失敗第五趟匹配s=ababcabcacbabi=4開始t=abca

20、ci=i-j+1;j=0; 進(jìn)入下一趟 j=0 i=10 j等于t的串長，匹配成功第六趟匹配s=ababcabcacbabi=5開始t=abcac返回i=i-n j=5 圖4.7BF算法的匹配過程算法4.6 有回溯的模式匹配算法。 int index(char s,char t,int start) int i,j,m,n; m=length(s); n=length(t); if(startm) return(-1); i=start; j=0; while(im & jn) if(si=tj) i+; j+; /* si=tj，比較下一個(gè) */ else /* si!=tj */ i=i-

21、j+1; j=0; /* sitj，i回到原位置+1，j回到0 */ if(jn) return(i-n); else return(-1); 上面所描述的算法中，若從某一個(gè)si開始與tj比較(j=0)，若si=tj，則i和j后移；若si!=tj，j回到原位置0，而i回到原位置加1。因?yàn)閖已經(jīng)從原來的位置向后移動(dòng)了j次，所以i也向后移動(dòng)了j次，故i的原位置為i-j，而原位置加1為i-j+1。同樣，當(dāng)匹配成功時(shí)，函數(shù)值返回i的原位置，這時(shí)j從0移動(dòng)到串t的結(jié)束(j=n)，即j向后移動(dòng)n次，同樣，i也應(yīng)向后移動(dòng)了n次，所以，函數(shù)返回值是i-n。這種有回溯的模式匹配算法在一些情況下，效率非常低，例如

22、， s=aaaaaaab 串長為n t=aab 串長為m，并且nm 這樣，每趟比較m次后匹配失敗，i回到原位置加1，j返回到0，繼續(xù)下一趟匹配,共計(jì)需要n-m趟。所以最壞情況下的時(shí)間復(fù)雜度為：O(n-m)*m)=O(n*m)，其原因是由每次匹配失敗，i回溯到原位置加1造成，下面我們討論無回溯的模式匹配算法。 4.4.2 無回溯的模式匹配算法(KMP算法) 算法的思想：是在每一趟匹配過程中，當(dāng)出現(xiàn)si不等于tj時(shí)，i不需要回溯到原位置加1(i保持不變)，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式串向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。 i=6 s6!=t4 匹配失敗第三趟匹配s=aba

23、bcabcacbabi=2開始t=abcaci=i-j+1;j=0; 進(jìn)入下一趟 j=4 例如，有回溯的匹配算法圖4.7，在該算法的第三趟匹配中，當(dāng)i=6和j=4字符不等時(shí)(si!=tj)，再次從i=3和j=0重新開始比較。但是，經(jīng)仔細(xì)觀察可以發(fā)現(xiàn)，在s3和t0，s4和t0以及s5和t0這三次比較都是不必進(jìn)行的。 因?yàn)閺牡谌瞬糠制ヅ涞慕Y(jié)果就可得出，主串中第4、5和6個(gè)字符必然是b、c和a(即模式串中第2、3和4個(gè)字符)，而模式串的第一個(gè)字符是a，因此它無需再和這三個(gè)字符進(jìn)行比較，僅需要將模式串指針j向右滑動(dòng)到第二個(gè)字符的位置(i保持不變)繼續(xù)進(jìn)行i=6和j=1時(shí)的字符比較即可。 i=2 s2

24、!=t2 匹配失敗第一趟匹配s=ababcabcacbabi=0開始t=abcaci=i-j+1;j=0; 進(jìn)入下一趟 j=2 同理，在第一趟匹配中，從i=0和j=0開始進(jìn)行比較，當(dāng)比較到i=2和j=2字符不等時(shí)(si!=tj)，i=6保持不變，而j滑動(dòng)到j(luò)=0的位置繼續(xù)進(jìn)行字符的比較。如圖4.8所示，在整個(gè)匹配過程中,i指針沒有回溯。 i=2 s2!=t2 匹配失敗第一趟匹配s=ababcabcacbabi=0開始t=abcaci=2不動(dòng);j滑動(dòng)到 0 j=2 i=2 i=6 s6!=t4 匹配失敗第一趟匹配s=ababcabcacbabi=0開始t=abcaci=6不動(dòng);j滑動(dòng)到1 j=0

25、 j=4 i=6 i=10j等于t的串長，匹配成功第一趟匹配s=ababcabcacbabi=0開始t=abcac返回i=i-n j=1 j=5圖4.8 無回溯算法的匹配過程例如主串s為ababcabcacbab，模式串t為abcac，無回溯的匹配過程如圖4.8所示。現(xiàn)在討論一般情況。每趟匹配失敗，根據(jù)子串t的特性使i不回溯，這時(shí)j退到恰當(dāng)?shù)哪硞€(gè)位置重新比較。 設(shè)主串為s0s1sn-1，模式串為t0t1tm-1，從主串s中某一個(gè)位置開始比較，當(dāng)匹配過程中產(chǎn)生“失配”(即si!=tj)時(shí)，指針i應(yīng)保持不變，如何設(shè)置j(si應(yīng)與模式串中的哪個(gè)tj字符比較)? 此時(shí)應(yīng)有： t0t1tj-1=si-j

26、si-j+1si-1 (4-1)假設(shè)此時(shí)j應(yīng)滑動(dòng)到j(luò)=k(kk(即si和tk進(jìn)行比較)，那么k具有以下性質(zhì)： t0t1tk-1=si-ksj-k+1si-1 (4-2) 同時(shí)利用已經(jīng)得到的“部分匹配”結(jié)果表達(dá)式(4-1)可知，這時(shí)應(yīng)有： tj-ktj-k+1tj-1=si-ksj-k+1si-1 ” (4-3) 再從表達(dá)式(4-2)和(4-3)可得到，于是對(duì)k的要求是： t0t1tk-1=tj-ktj-k+1tj-1 (4-4) 通俗說法是：當(dāng)模式中tj與主串中si失配時(shí)，將si與tk比較，所取k的原則：模式串的前k個(gè)字符子串等于tj前的k個(gè)字符子串，并且是具有此性質(zhì)的最大子串的串長。如圖4.

27、9所示。圖4.9 模式串的特征 反之，若模式串中存在滿足(4-4)的兩個(gè)子串，則當(dāng)匹配過程中，主串中第i個(gè)字符與模式串中第j個(gè)字符比較不等時(shí)，僅需要將模式串向右滑動(dòng)至模式串中第k個(gè)字符和主串中第i個(gè)字符對(duì)齊，此時(shí)，模式串中頭k個(gè)字符的子串t0t1tk-1必定與主串中第i個(gè)字符之前長度為k的子串si-ksj-k+1si-1相等。 如在圖4.8中，當(dāng)?shù)诙似ヅ洹笆洹睍r(shí)，i=6不變，此時(shí)在模式串t0到tj-1(即t3)中，滿足此性質(zhì)的最大子串為a，所以k取1，即從i=6和j=1進(jìn)行第三趟匹配。在模式串中，對(duì)于不同的tj有不同的tk，于是設(shè)一個(gè)數(shù)組nextj=k，用于存儲(chǔ)各字符tj的對(duì)應(yīng)tk的k值。

28、具體求nextj的原則若下： (1)j=0時(shí)，nextj=-1。 (2)存在t0t1tk-1=tj-ktj-k+1tj-1(0kj)，則 取k的最大值。 (3)否則，nextj=0。 j 0 1 2 3 4 5 6 模式串 a a a a a a bNextj-1 0 1 2 3 4 5 j 0 1 2 3 4 5 6 模式串 a a a a a a bNextj-1 0 1 2 3 4 5例4.1例4.2 因?yàn)閚ext數(shù)組只與模式串相關(guān)，所以可以預(yù)先求出。 假設(shè)next已經(jīng)求得，則KMP的模式匹配算法用C語言描述下：算法4.8 KMP的模式匹配算法。 int index_kmp(char s

29、,char t,int next) /* 從主串s起始位置開始查找 */ int i=0, j=0, m, n; m=strlen(s); n=strlen(t); while(im & j=n) return(i-n); else return(-1); 求next的算法又是如何實(shí)現(xiàn)的？ 由定義可知： next0=-1設(shè) nextj=k，這表明在模式串中 t0t1tk-1”=”tj-ktj-k+1tj-1其中k為滿足0kk滿足上式。此時(shí)nextj+1=?可能有兩種情況： (1)若tk=tj，則表明在模式串中 t0t1tk-1tk=tj-ktj-k+1tj-1tj并且，不可能存在kk滿足上式，

30、這就是說nextj+1=k+1，即 nextj+1=nextj+1 (2)若tk!=tj，則表明在模式串中 t0t1tk-1tk!= tj-ktj-k+1tj-1tj 此時(shí)可以把求next數(shù)組問題看成是一個(gè)模式匹配問題，整個(gè)模式串既是主串又是模式串，而當(dāng)前在匹配過程中，已有t0=tj-k ，t1=tj-k+1，tk-1=tj-1，則當(dāng)tk!=tj時(shí)應(yīng)將模式串向右滑動(dòng)以至于使模式串中第k=nextk個(gè)字符和主串中的第j個(gè)字符比較，若tk =tj ，則說明在主串中第j+1個(gè)字符前存在一個(gè)長度為k+1的最長子串，和模式串中頭k+1個(gè)字符組成的子串相等，即 t0t1tk-1tk != tj-ktj-k+1tj-1tj這就是說 nextj+1=k+1，即 nextj+1=nextk+1同理，若tk!=tj，則將模式繼續(xù)向右滑動(dòng)直至將模式中第k=nextk個(gè)字符和tj對(duì)齊，依次類推，直至tj和模式中某個(gè)字符匹配成功或者不存在任何k(0kj)滿足等式t0t1tk-1tk != tj-ktj-k+1tj-1tj，則 nextj+1=0 例如，模式串t=abaabcac，如圖4.10所示，已求得前6個(gè)字符的next值，現(xiàn)在要求next6，因?yàn)閚ext5=2，又t5!=t2，則需要比較t5和t1(因?yàn)閚ext2=0