串類型的定義串的表示與實(shí)現(xiàn)的模式匹配算法串操作應(yīng)用舉例課件_第1頁(yè)
串類型的定義串的表示與實(shí)現(xiàn)的模式匹配算法串操作應(yīng)用舉例課件_第2頁(yè)
串類型的定義串的表示與實(shí)現(xiàn)的模式匹配算法串操作應(yīng)用舉例課件_第3頁(yè)
串類型的定義串的表示與實(shí)現(xiàn)的模式匹配算法串操作應(yīng)用舉例課件_第4頁(yè)
串類型的定義串的表示與實(shí)現(xiàn)的模式匹配算法串操作應(yīng)用舉例課件_第5頁(yè)
已閱讀5頁(yè),還剩50頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、串類型的定義串的表示和實(shí)現(xiàn)串的模式匹配算法串操作應(yīng)用舉例第四章 串第1頁(yè),共55頁(yè)。1、了解串的概念;學(xué)習(xí)要點(diǎn)2、熟悉串的基本運(yùn)算的定義 及實(shí)現(xiàn)方法;3、掌握基本串匹配算法。第2頁(yè),共55頁(yè)。 在較早的程序設(shè)計(jì)語(yǔ)言中,字符串(簡(jiǎn)稱串)是作為輸入或輸出的常量(是直接量,不參加運(yùn)算)出現(xiàn),而非數(shù)值處理的對(duì)象基本上是字符串?dāng)?shù)據(jù)。這就要求字符串也能以變量的形式出現(xiàn),能進(jìn)行一系列字符串操作(運(yùn)算) 。目前大多數(shù)程序設(shè)計(jì)語(yǔ)言都支持串這種數(shù)據(jù)類型。第3頁(yè),共55頁(yè)。 1、串 2、串長(zhǎng):串中所包含的字符個(gè)數(shù)。 3、空串 :長(zhǎng)度為零的串,它不包含任何字符。 記作“” 4、子串:串中任意個(gè)連續(xù)的字符組成的子序列。

2、 5、主串:包含子串的串。 4.1 串類型的定義 基本概念 :零個(gè)或多個(gè)字符組成的有限序列,即數(shù) 據(jù)元素為字符的線性表。一般記為 S=a1a2. an ,其中,S是串名, 單引號(hào)括起的字符序列是串值。 第4頁(yè),共55頁(yè)。7、子串在主串中的位置 :子串在主串中第一次出現(xiàn)時(shí),子串的第一個(gè)字符在主串中的位置。6、字符在串中的位置:字符在序列中的序號(hào)。 8、兩個(gè)串相等 :兩個(gè)串的長(zhǎng)度相等,并且各 個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等。9、空格串 : 由一個(gè)或多個(gè)空格組成的串,其長(zhǎng)度為串中空格字符的個(gè)數(shù)。它與空串是不同的概念。 第5頁(yè),共55頁(yè)。 串的邏輯結(jié)構(gòu)和線性表極為相似,區(qū)別僅在于串的數(shù)據(jù)對(duì)象為字符集。

3、 串的基本操作和線性表有很大差別: 在線性表的基本操作中,大多以“單個(gè)元素”作為操作對(duì)象; 在串的基本操作中,通常以“串的整體”作為操作對(duì)象 。第6頁(yè),共55頁(yè)。 ADT String 數(shù)據(jù)對(duì)象:D ai |aiCharacterSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系:R1 | ai-1, ai D, i=2,.,n 基本操作: ADT StringADT串的定義第7頁(yè),共55頁(yè)。StrAssign (&T, chars) /串賦值 初始條件:chars 是字符串常量。 操作結(jié)果:把 chars 賦為 T 的值。 StrCopy (&T, S) /串復(fù)制 初始條件:串 S 存在。 操作

4、結(jié)果:由串 S 復(fù)制得串 T。DestroyString (&S) /串銷毀 初始條件:串 S 存在。 操作結(jié)果:串 S 被銷毀。第8頁(yè),共55頁(yè)。 StrEmpty(S) /串判空初始條件:串S存在。操作結(jié)果:若 S 為空串,則返TRUE, 否則返回 FALSE。StrCompare(S,T) /串比較例如:StrCompare(data, state) 0初始條件:串 S 和 T 存在。操作結(jié)果:若S T,則返回值 0; 若S T,則返回值 0; 若S T,則返回值 0第9頁(yè),共55頁(yè)。StrLength (S) /求串長(zhǎng)初始條件:串 S 存在。操作結(jié)果:返回 S 的元素個(gè)數(shù), 稱為串的長(zhǎng)

5、度。Concat (&T, S1, S2) /串聯(lián)接例如: Concate( T, man, kind) 求得 T = mankind初始條件:串 S1 和 S2 存在。操作結(jié)果:用 T 返回由 S1 和 S2 聯(lián)接而成的新串。第10頁(yè),共55頁(yè)。 SubString (&Sub, S, pos, len) /求子串 初始條件: 串 S 存在,1posStrLength(S) 且0lenStrLength(S)-pos+1。 操作結(jié)果:用 Sub 返回串 S 的第 pos 個(gè)字符起長(zhǎng)度為 len 的子串。子串為“串”中的一個(gè)字符子序列。第11頁(yè),共55頁(yè)。 SubString( sub, co

6、mmander, 1, 9) 求得 sub = commander SubString( sub, commander, 9, 1) 求得 sub = r 例如: SubString( sub, commander, 4, 3) 求得 sub = man;第12頁(yè),共55頁(yè)。SubString(sub , student, 5, 0) 得sub= 關(guān)于參數(shù)len(子串長(zhǎng)度)的說(shuō)明:長(zhǎng)度為 0 的子串為“合法”串空串。事實(shí)上對(duì)任何串S和位置pos 都有:SubString(sub, commander, 4, 7) 得sub = manderSubString(sub , S, pos, 0)得

7、sub= ;有時(shí)對(duì)len放寬到lenStrLength(S)-pos+1,此時(shí)規(guī)定 SubString(sub ,S, pos, len) 的值取S的第pos個(gè)字符到S的最后一個(gè)字符作為子串(長(zhǎng)為StrLength(S)-pos+1)。第13頁(yè),共55頁(yè)。Index (S, T, pos) /(子)串(位置)定位 初始條件:串S和T存在,T是非空串, 1posStrLength(S)。 操作結(jié)果:若主串 S 中存在和串T值相同 的子串, 則返回它在主串S中第 pos個(gè)字符之后第一次出現(xiàn)的位 置;否則函數(shù)值為0。第14頁(yè),共55頁(yè)。假設(shè) S = abcaabcaaabc, T = bca Ind

8、ex(S, T, 1) =Index(S, T, 3) = Index(S, T, 8) = “子串在主串中的位置”意指子串中的第一個(gè)字符在主串中的位序。2;6;0;第15頁(yè),共55頁(yè)。Replace (&S, T, V) /串替換初始條件:串S, T和 V 均已存在, 且 T 是非空串。操作結(jié)果:用V替換主串S中出現(xiàn)的所有與 (模式串) T相等的不重疊的子串。 例如:假設(shè)S=abcaabcaaabca, T = bca若V=x,則經(jīng)置換后得到S=axaxaax若V=bc,則經(jīng)置換后得到S=abcabcaabc 第16頁(yè),共55頁(yè)。 StrInsert (&S, pos, T) /串插入例如:

9、S = chater,T = rac, 則執(zhí)行 StrInsert(S, 4, T)之后得到 S = character初始條件:串S和T存在, 1posStrLength(S)1。操作結(jié)果:在串S的第pos個(gè)字符之前插入 串T。 第17頁(yè),共55頁(yè)。StrDelete (&S, pos, len) /串刪除 初始條件:串S存在 , 1posStrLength(S)-len+1。 操作結(jié)果:從串S中刪除第pos個(gè)字符 起長(zhǎng)度為len的子串。 ClearString(&S) /串清除初始條件:串S存在。操作結(jié)果:將S清為空串。第18頁(yè),共55頁(yè)。在上述抽象數(shù)據(jù)類型定義的13種操作中, 串賦值St

10、rAssign、串復(fù)制Strcopy、 串比較StrCompare、求串長(zhǎng)StrLength、 串聯(lián)接Concat以及求子串SubString 等六種操作構(gòu)成串類型的最小操作子集。 這些操作不可能利用其他串操作來(lái)實(shí)現(xiàn), 反之,其他串操作(除串清除ClearString和串 銷毀DestroyString外)可在這個(gè)最小操作子 集上實(shí)現(xiàn)。第19頁(yè),共55頁(yè)。 例如,可利用串比較、求串長(zhǎng)和求子串等操作實(shí)現(xiàn)定位函數(shù)Index(S,T,pos)。 StrCompare(SubString(S, i, StrLength(T),T ) T 串 T 串iposStrLength(S) StrLength(

11、T) +1算法的基本思想:? = 0S 串 在pos到StrLength(S) StrLength(T) +1范圍內(nèi)尋求使下式成立的i值 T 串ipos+1第20頁(yè),共55頁(yè)。int Index (String S, String T, int pos) / T為非空串。若主串S中第pos個(gè)字符之后存在與 T相等的/子串,則返回第一個(gè)這樣的子串在S中的 位置,否則返回0 if (pos 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompa

12、re(sub,T) != 0) +i ; else return i ; return 0; / S中不存在與T相等的子串 / Index第21頁(yè),共55頁(yè)。 利用最小操作子集中的操作也可實(shí)現(xiàn) 串判空 StrEmpty(S) 、 串替換 Replace (&S, T, V) 、 串刪除 StrDelete (&S, pos, len) 、 串插入 StrInsert (&S, pos, T) 等操作。留作習(xí)題第22頁(yè),共55頁(yè)。 若在程序設(shè)計(jì)語(yǔ)言中,串只是作為輸入或輸出的常量出現(xiàn),則只需存儲(chǔ)此串的串值,即字符序列即可。但在多數(shù)非數(shù)值處理的程序中,串也以變量的形式出現(xiàn)。4.2 串的表示和實(shí)現(xiàn) 串

13、有三種機(jī)內(nèi)表示方法: 一、串的定長(zhǎng)順序存儲(chǔ)表示二、串的堆分配存儲(chǔ)表示三、串的塊鏈存儲(chǔ)表示第23頁(yè),共55頁(yè)。 用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列。該結(jié)構(gòu)可用定長(zhǎng)數(shù)組描述如下: #define MAXSTRLEN 255 /可在255以內(nèi)定義最大串長(zhǎng) typedef unsigned char Sstring MAXSTRLEN + 1; / 0號(hào)單元存放串的長(zhǎng)度一、串的定長(zhǎng)順序存儲(chǔ)表示第24頁(yè),共55頁(yè)。 對(duì)串的長(zhǎng)度有兩種表示方法: 1.以下標(biāo)為0的數(shù)組分量存放串的實(shí)際長(zhǎng)度 (如 PASCAL語(yǔ)言) ,特點(diǎn)是便于進(jìn)行某些操作; 2.在串值后面加不計(jì)入串長(zhǎng)的結(jié)束標(biāo)記字符(如C 語(yǔ)言采用“

14、0” ) ,此時(shí)的串長(zhǎng)為隱含值,特點(diǎn)是 訪問(wèn)容易,但刪除或插入麻煩。說(shuō)明: 串的實(shí)際長(zhǎng)度可在預(yù)定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定, 超過(guò)預(yù)定義長(zhǎng)度的串值則被 “截?cái)唷?。 對(duì)超長(zhǎng)部分實(shí)施截?cái)嗖僮髡谴亩ㄩL(zhǎng)順序存儲(chǔ) 表示的弊端。為克服此弊端,惟有不限定最大串 長(zhǎng),即動(dòng)態(tài)分配串值的存儲(chǔ)空間。第25頁(yè),共55頁(yè)。 以下以串聯(lián)接為例進(jìn)行討論在這種存儲(chǔ)結(jié)構(gòu)表示下如何實(shí)現(xiàn)串的操作: 假設(shè)T, S1, S2都是 Sstring型變量, T為S1聯(lián)結(jié)S2后所得之串,則聯(lián)接運(yùn)算Concat (&T, S1, S2) 是將S1和S2的值分別傳送到T的相應(yīng)位置上,超過(guò)MAXSTRLEN的部分截?cái)嘀?其運(yùn)算結(jié)果可能有三種情

15、況: 1) S10+ S20 MAXSTRLEN 2) S10+ S20 MAXSTRLEN 3) S10 MAXSTRLEN第26頁(yè),共55頁(yè)。1) S10+ S20 MAXSTRLEN串S1串S2串 TS10S20S10+ S20MAXSTRLENMAXSTRLENMAXSTRLEN第27頁(yè),共55頁(yè)。2) S10+ S20 MAXSTRLEN串 S1串 S2串 TS10S20MAXSTRLENMAXSTRLENMAXSTRLEN截去第28頁(yè),共55頁(yè)。 串S2被全部截去。3) S10 MAXSTRLEN串 S1串 S2串 TS10S20S10MAXSTRLENMAXSTRLENMAXST

16、RLEN第29頁(yè),共55頁(yè)。Status Concat(SString &T, SString S1, SString S2) if (S10+S20 = MAXSTRLEN) / 不截?cái)?T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; else / 截?cái)?if ( S10 MAXSTRSIZE ) T1.S10 = S11.S10;TS10+1.MAXSTRLEN = S21.MAXSTRLENS10;T0 = MAXSTRLEN; uncut = FALSE; 第30頁(yè),共55頁(yè)。 else T

17、0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; return uncut; / Concat 在串的順序存儲(chǔ)結(jié)構(gòu)中,實(shí)現(xiàn)串操作的原操作為“字符序列的復(fù)制”,操作的時(shí)間復(fù)雜度基于字符序列的長(zhǎng)度。第31頁(yè),共55頁(yè)。二、串的堆分配存儲(chǔ)表示 堆分配存儲(chǔ)類似于線性表的順序存儲(chǔ)結(jié)構(gòu),仍以一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列,但它們的存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得的。在C語(yǔ)言中是由動(dòng)態(tài)分配函數(shù)malloc()和free()來(lái)管理一個(gè)稱之為“堆(heap)”的自由存儲(chǔ)區(qū)的。該存儲(chǔ)結(jié)構(gòu)類型描述如下:typedef

18、 struct char *ch ; / 若是非空串,則按串長(zhǎng)分配存儲(chǔ)區(qū), /否則ch為NULL int length; / 串長(zhǎng)度 一個(gè)串值的確定是通過(guò)串在堆中的起始位置和串的長(zhǎng)度實(shí)現(xiàn)的。HString;第32頁(yè),共55頁(yè)。 這類串操作實(shí)現(xiàn)的算法為: 先為新生成的串(若該串已存在,則先釋放其所占空間)分配一個(gè)長(zhǎng)度適當(dāng)?shù)拇鎯?chǔ)空間,然后進(jìn)行串值的復(fù)制。這種存儲(chǔ)結(jié)構(gòu)表示時(shí)的串操作仍基于 “字符序列的復(fù)制” 進(jìn)行的。為此,串名與串值之間要建立一個(gè)對(duì)照表。 0 1 2 3 4 5 6 7 8 9 HString a,b ;串名 基址 ch 長(zhǎng)度 length a 2000 4 b 2012 4 D a

19、 t a S t r u c t u r e B o o k 16 2000第33頁(yè),共55頁(yè)。 串插入算法Status StrInsert (Hstring &S, int pos, Hstring T) /在串S的第pos個(gè)字符之前插入串T S.ch0 1 pos-1T.lengthif (pos S.length+1) return ERROR; if ( T.length ) /T非空,則重新分配空間,插入Tif(!(S.ch=(char *) ralloc(S.ch , (S.length +T.length) *sizeof(char) exit(OVERELOW) ; for(

20、i=S.length-1;i pos - 1;-i ) /插入T而騰出位置 S.chi +T.length= S.chi ;第34頁(yè),共55頁(yè)。 S.chpos - 1. pos +T.length - 2= T.ch0. T.length - 1; /插入T S.length = T.length; return OK ; 第35頁(yè),共55頁(yè)。堆分配存儲(chǔ)結(jié)構(gòu)表示時(shí)的(只含最小操作子集)基本操作的算法描述Status StrAssign(HString &T,char *chars) /生成一個(gè)其值等于串常量chars的串Tif(T.ch) free(T.ch); /若串T已存在,釋放其所占空

21、間for ( i=0, c=chars ; c ; +i, +c );if ( ! i ) T.ch=null; T.length=0; else if( ! ( T.ch = ( char * )malloc(i*sizeof(char) exit(OVERFLOW); T.ch0.i-1=chars0.i-1; T.length=i; return OK ; 第36頁(yè),共55頁(yè)。int StrLength(HString s) return s.length; int StrCmpare(HString S , HString T) for(i=0; iS.length & iT.leng

22、th; +i) if(S.chi!=T.chi ) return(S.chi T.chi); return S.lengthT.length; Status ClearString(HString &S) if(S.ch) free(S.ch); s.ch=null; S.length=0; return OK; 第37頁(yè),共55頁(yè)。Status Concat(HString &T, HString S1, HString S2) / 用T返回由S1和S2聯(lián)接而成的新串 if (T.ch) free(T.ch); / 釋放舊空間 if (!(T.ch = (char *) malloc ( (

23、S1.length+S2.length)*sizeof(char) exit (OVERFLOW); T.ch0.S1.length-1 = S1.ch0.S1.length-1; T.length = S1.length + S2.length; T.chS1.length.T.length-1 = S2.ch0.S2.length-1; return OK; / Concat第38頁(yè),共55頁(yè)。 Status SubString(HString &Sub, HString S, int pos, int len) if (pos S.length | len S.length-pos+1)

24、 return ERROR;if ( Sub.ch ) free ( Sub.ch ); / 釋放舊空間 if ( ! len ) Sub.ch = NULL; Sub.length = 0; / 空子串 else / 完整子串 Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len; return OK; / SubString第39頁(yè),共55頁(yè)。三、串的塊鏈存儲(chǔ)表示 可采用鏈表方式存儲(chǔ)串值,每個(gè)結(jié)點(diǎn)可以存放一個(gè)字符,也可以存放多個(gè)字符 (如圖所示)。 為便于進(jìn)行

25、串的操作,當(dāng)以鏈表存儲(chǔ)串值時(shí),還需增設(shè)尾指針指示鏈表中的最后一個(gè)結(jié)點(diǎn),并給出當(dāng)前串的長(zhǎng)度,如此定義的結(jié)構(gòu)就稱為塊鏈結(jié)構(gòu).描述如下:A B C DE F G HI # # #head head A B C I 第40頁(yè),共55頁(yè)。#define CHUNKSIZE 80 / 可由用戶定義的塊大小typedef struct Chunk / 結(jié)點(diǎn)結(jié)構(gòu) char chCHUNKSIZE; struct Chunk *next; Chunk;typedef struct / 串的鏈表結(jié)構(gòu) Chunk *head, *tail; / 串的頭和尾指針 int curlen; / 串的當(dāng)前長(zhǎng)度 LStrin

26、g;第41頁(yè),共55頁(yè)。 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,結(jié)點(diǎn)大小的選擇直接影響著串處理的效率。在各種串的處理系統(tǒng)中,所要處理的串往往很長(zhǎng)或很多。因此需考慮串的存儲(chǔ)密度。存儲(chǔ)密度 = 數(shù)據(jù)元素所占存儲(chǔ)位實(shí)際分配的存儲(chǔ)位 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類似線性鏈表,由于串結(jié)構(gòu)的特殊性, 要考慮每個(gè)結(jié)點(diǎn)是存放一個(gè)字符還是多個(gè)字符。一個(gè)字符的,插入、刪除、求長(zhǎng)度非常方便,但存儲(chǔ)效率低。 多個(gè)字符的,改善了效率,在處理不定長(zhǎng)的大字符串時(shí)很有效,但插入、刪除不方便,可用特殊符號(hào)來(lái)填滿未充分利用的結(jié)點(diǎn)。 第42頁(yè),共55頁(yè)。 例如: 在編輯系統(tǒng)中,整個(gè)文本編輯區(qū)可以看成是一個(gè)串,每一行是一個(gè)子串,構(gòu)成一個(gè)結(jié)點(diǎn)。即: 同一行的串用定長(zhǎng)結(jié)構(gòu)

27、(80個(gè)字符), 行和行之間用指針相聯(lián)接。 實(shí)際應(yīng)用時(shí),可以根據(jù)問(wèn)題所需來(lái)設(shè)置結(jié)點(diǎn)的大小。第43頁(yè),共55頁(yè)。4.3串的模式匹配算法 子串位置定位操作Index( S , T , pos )通常稱作串的模式匹配(其中T被稱為模式串),是各種串處理系統(tǒng)中最重要的操作之一。很多軟件若有“編輯”菜單項(xiàng)的話,則其中必有“查找”子菜單項(xiàng)。查找即為模式匹配。第44頁(yè),共55頁(yè)。INDEX (S, T, pos)初始條件:串S和T存在,T是非空串, 1posStrLength(S)。操作結(jié)果:若主串S中存在和串T值相同的 子串返回它在主串S中第pos個(gè)字符之后 第一次出現(xiàn)的位置; 否則函數(shù)值為0 。 回憶一

28、下串定位操作的定義:第45頁(yè),共55頁(yè)。模式匹配的算法的基本思想: 從主串S的第 pos個(gè)字符起和模式串T的第一個(gè)字符比較,若相等,則逐個(gè)比較后續(xù)字符;否則從S的下一個(gè)字符起再重新和T的字符比較。依此類推,直至T中的每個(gè)字符依次和S 中一個(gè)連續(xù)的字符序列相等為止,則稱匹配成功,返回與T中第一個(gè)字符相等的字符在S中的序號(hào);否則稱匹配不成功,返回零。 為此,設(shè)置主串指針i和模式串指針j指示當(dāng)前兩串對(duì)應(yīng)位置上的 (待比較的)字符。 以下展示模式T=abcac和主串S=ababcabcacbab的匹配過(guò)程:第46頁(yè),共55頁(yè)。a b a b c a b c a c b a b第一趟匹配 i=1.a b

29、 c a ca b a b c a b c a c b a b第三趟匹配 i=3.第四趟匹配 i=4.第五趟匹配 i=5.第六趟匹配 i=6.匹配成功第二趟匹配 i=2.a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca b c a ca b c a ca b c a c327411j=1.j=1.j=1.j=1.j=1.j=1.3111655T0第47頁(yè),共55頁(yè)。以定長(zhǎng)順序結(jié)構(gòu)表示串時(shí)的簡(jiǎn)單算法(不依賴于

30、其它串操作)int Index(SString S, SString T, int pos) i = pos; j = 1; while ( i S0 & j T0) /匹配成功( T0 個(gè)對(duì)應(yīng)位置上的字符相同) return i-T0; /返回子串在主串中的位置 else return 0; / Index 本算法思路簡(jiǎn)單,匹配過(guò)程易于理解,通常稱作樸素的匹配算法。在某些應(yīng)用場(chǎng)合,如文本編輯,效率也較高。但當(dāng)主串中存在多個(gè)與模式串“部分匹配”的子串時(shí),就引起主串指針i的多次回溯,從而降低匹配效率。以下介紹的KMP算法就是一種改進(jìn)算法,其改進(jìn)在于:不需回溯i指針,而是利用已得“部分匹配”的結(jié)果將模式串盡可能遠(yuǎn)地向右“滑動(dòng)”。第49頁(yè),共55頁(yè)。 以模式T=abcac和主串S=ababcabcacbab的匹配過(guò)程為例簡(jiǎn)但介紹KMP算法:a b a b c a b c a c b a b第一趟匹配 i=1.a b c a c第三趟匹配 i=3.第四趟匹配 i=4.第五趟匹配 i=5.第六趟匹配 i=6.匹配成功a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論