1、1,數(shù)據(jù)結(jié)構(gòu)4串,2,開始學(xué)習(xí)本章前要知道：,從數(shù)據(jù)結(jié)構(gòu)角度看，串也屬于線性結(jié)構(gòu)，具有線性結(jié)構(gòu)的共同特征； 學(xué)習(xí)本章時(shí)，要注意到串所具有的線性結(jié)構(gòu)的共性，更要掌握其個(gè)性； 串的特殊性主要是：串的元素是字符。,3,主要內(nèi)容,串的基本概念 串的基本操作 串的存儲(chǔ)結(jié)構(gòu) 定長(zhǎng)順序存儲(chǔ) 塊鏈存儲(chǔ) 串的模式匹配 簡(jiǎn)單算法 KMP算法,4,串的基本概念,串的定義 串：n個(gè)字符的有限序列，n=0 一般記為：S = a1 a2. an 其中，S是串名，a1 a2. an是串S的值，串值必須由一對(duì)單引號(hào)括起來 串的長(zhǎng)度：串中字符的個(gè)數(shù),例如,S1=abc S2=FORTRAN_77 S3=(空串),長(zhǎng)度為0,5,

2、串的基本概念,幾個(gè)名詞概念,1.子串：串中若干個(gè)連續(xù)的字符組成的子序列。 例如：S = Beijing,但最多只能存放255個(gè)字符，因?yàn)楸仨毩粢蛔止?jié)來存放串終結(jié)符0。,10,串的存儲(chǔ)結(jié)構(gòu)：定長(zhǎng)順序表示,若不設(shè)置終結(jié)符，可用一個(gè)整數(shù)length來表示串的長(zhǎng)度，此時(shí)順序串的類型定義完全和順序表類似：,s.data,typedef struct char chmaxsize ; /串的存儲(chǔ)空間 int curlen ; /當(dāng)前串的長(zhǎng)度 SeqString ;,11,串的表示和實(shí)現(xiàn)：定長(zhǎng)順序表示,串的拼接 S10+S20 = maxsize,12,串的表示和實(shí)現(xiàn)：定長(zhǎng)順序表示,串的拼接 S10+S20

3、 maxsize S10 maxsize,13,串的表示和實(shí)現(xiàn)：定長(zhǎng)順序表示,串的拼接 S10 = maxsize,14,串的表示和實(shí)現(xiàn)：定長(zhǎng)順序表示,求子串 串S第i個(gè)字符起，長(zhǎng)度為j的子串,S,i,j,15,串的表示和實(shí)現(xiàn)：鏈接存儲(chǔ),鏈接存儲(chǔ),串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。其結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符： typedef struct linknode char data; struct linknode *next; linkstring;,直接使用線性鏈表來存儲(chǔ)字符串：效率太低,16,說明 所謂鏈結(jié)點(diǎn)大小是指每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中存放的字符的個(gè)數(shù)。,例如：S=DATA STRUCTURE,串的表示

4、和實(shí)現(xiàn)：鏈接存儲(chǔ),17,在上圖中第3個(gè)字符后插入vwxyz的鏈串,S1,結(jié)點(diǎn)大小為4的鏈串,S1,串的表示和實(shí)現(xiàn)：鏈接存儲(chǔ),對(duì)于結(jié)點(diǎn)數(shù)據(jù)域大于1的鏈串，其類型定義如下： #define nodesize 80 typedef struct node char datanodesize;/結(jié)點(diǎn)存的字符個(gè)數(shù) struct node *next; LinkStrNode1;,18,串的表示和實(shí)現(xiàn)：鏈接存儲(chǔ),優(yōu)點(diǎn) 便于拼接操作 缺點(diǎn) 結(jié)點(diǎn)大小需要設(shè)置恰當(dāng) 存儲(chǔ)密度 = 結(jié)點(diǎn)越小，存儲(chǔ)密度越小，操作越方便，但是存儲(chǔ)空間浪費(fèi)大,19,模式匹配(在主串S中定位子串T（模式串）) 回憶一下串匹配的定義： in

5、dex(S,T) 初始條件：串S和T存在 操作結(jié)果：若主串S中存在和串T值相同的子串，返回它在主串S首次出現(xiàn)的位置；否則返回0 例如 主串S = 子串T = CD 則index(S,T)，返回子串T在S中，第一次出現(xiàn)的位置3,串的模式匹配,20,串的模式匹配,Brute-Force算法基本思想： 從目標(biāo)串s 的第一個(gè)字符起和模式串t的第一個(gè)字符進(jìn)行比較 若相等，則繼續(xù)逐個(gè)比較后續(xù)字符，否則從串s 的第二個(gè)字符起再重新和串t進(jìn)行比較。 依此類推，直至串t 中的每個(gè)字符依次和串s的一個(gè)連續(xù)的字符序列相等，則稱模式匹配成功，此時(shí)串t的第一個(gè)字符在串s 中的位置就是t 在s中的位置，否則模式匹配不成功

6、。,21,Brute-Force算法的C語言描述如下： int Index(string s,string t) int i=0,j=0; /i,j分別指向串s、t的第1個(gè)字符 while( (i=t.curlen ) return( i-t.curlen ); /匹配成功，返回串t在串s中起始位置 else return 0; /匹配失敗返回0 ,22,while(is.curlen) ,23,串的模式匹配:簡(jiǎn)單算法,算法分析 最好的情況 主串S和模式T中的每個(gè)字符都只訪問了一次 復(fù)雜度 = O( n+m ),24,最差的情況 主串S中的每個(gè)字符，分別和模式T中的每個(gè)字符匹配一次 復(fù)雜度 =

7、 O( n*m ),串的模式匹配:簡(jiǎn)單算法,25,由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出了一個(gè)改進(jìn)算法，消除了Brute-Force算法中串s指針的回溯，完成串的模式匹配。 基本思想：在簡(jiǎn)單算法的基礎(chǔ)上，i不要回退，模式串盡量多往右移 時(shí)間復(fù)雜度為O(s.curlen+t.curlen)，這就是Knuth-Morris-Pratt算法，簡(jiǎn)稱KMP 算法。,串的模式匹配:KMP算法,26,利用已經(jīng)部分匹配的結(jié)果信息，盡量讓i不要回溯，加快模式串的滑動(dòng)速度。例：,S=ababcabcacbab,T=abcac,aba,abc,S=ababcabcacbab,T=ab

8、cac,S=ababcabcacbab,T=abcac,需要討論兩個(gè)問題： 如何由當(dāng)前部分匹配結(jié)果確定模式串向右滑動(dòng)的新比較起點(diǎn)k？ 模式串應(yīng)該向右滑多遠(yuǎn)才是高效率的?,27,請(qǐng)抓住部分匹配時(shí)的兩個(gè)特征：,設(shè)S的第i字符目前打算與T的第k字符開始比較,k是追求的新起點(diǎn),則T的k-10=S前i-1i-k位匹配,“T0Tk-1”,(2),剛才肯定是在S的i處和T的第j字符處失配,則T的j-1j-k位=S前i-1i-k位匹配,“Tj-kTj-1”截取一段，但k有限制，0kj,兩式聯(lián)立可得：“T0Tk-1”= “Tj-kTj-1”,注意：j為當(dāng)前已知的失配位置，我們的目標(biāo)是計(jì)算新起點(diǎn)k。式中僅剩一個(gè)未

9、知數(shù)k，理論上已可解！,奇妙的結(jié)果：k僅與模式串T有關(guān)！,28,根據(jù)模式串T的規(guī)律：“T0Tk-1”=“Tj-k Tj-1” 由當(dāng)前失配位置j(已知)，歸納計(jì)算新起點(diǎn)k的表達(dá)式。,新起點(diǎn)k怎么求？,nextj=,0 當(dāng)j=1時(shí) max k|1kj且T0Tk-1=Tj-k Tj-1 1 其他情況,注意： (1)k值僅取決于模式串本身而與相匹配的主串無關(guān)。 (2)k值為模式串從頭向后及從j向前的兩部分的最大相同子串的長(zhǎng)度。 (3)這里兩部分子串可以有部分重疊的字符，但不可以全部重疊。,令k = nextj（k與j顯然具有函數(shù)關(guān)系），則,取T首與Tj處最大的相同子串,29,nextj函數(shù)表示模式T中

10、最大相同前綴子串和后綴子串（真子串）的長(zhǎng)度。 可見，模式中相似部分越多，則nextj函數(shù)越大，它既表示模式T字符之間的相關(guān)度越高，也表示j位置以前與主串部分匹配的字符數(shù)越多。 即：nextj越大，模式串向右滑動(dòng)得越遠(yuǎn)，與主串進(jìn)行比較的次數(shù)越少，時(shí)間復(fù)雜度就越低（時(shí)間效率）。,30,i、j分別為指示s(目標(biāo)串)和t(模式串)的指針，初值均為1。 若 si = tj，則i和j分別增1； 否則，i不變，j退回至j=nextj的位置(即串s不動(dòng)，模式串t向右移動(dòng)到 si與tnextj 對(duì)齊)； 比較 si 和 tj。若相等則指針各增1；否則j再退回到下一個(gè)j=nextj的位置(即模式串繼續(xù)向右移動(dòng))，

11、再比較 si 和 tj 。,KMP算法的基本思想,依次類推，直到下列兩種情況之一： 1)j退回到某個(gè)j=nextj時(shí)有 si = tj，則指針各增1，繼續(xù)匹配； 2)j退回至j=0，此時(shí)令指針各增1，即下一次比較 si+1和 t0 。,31,串的模式匹配：KMP算法,模式串的next函數(shù) 意義：j之前的子串中，左起一段=右起一段，最長(zhǎng)可以到k,32,串的模式匹配：KMP算法,例如：,33,串的模式匹配：KMP算法,此次匹配失敗 讓 j = nextj = 3,34,KMP算法,理解 Si!=Tj，說明i之前的字符都匹配 則S4.5=T4.5 nextj=3，說明T1.2=T4.5 因此T1.2

12、=S4.5,S T,35,KMP算法,疑問1：子串T會(huì)不會(huì)向前走得太多了？ 假設(shè)只向前走一個(gè)字節(jié)可不可能呢？ 如果可以的話，則T1.4=S2.5 而剛才已知T1.5=S1.5 則S1.4=S2.5 也就是T1.4=T2.5 那么next6=5，和已知的next6=3矛盾！,S T,36,KMP算法,同理：向前走2個(gè)字節(jié)也不可能 如果可以的話，則T1.3=S3.5 而剛才已知T1.5=S1.5 則S1.3=S3.5 也就是T1.3=T3.5 那么next6=4，和已知的next6=3矛盾！,S T,37,KMP算法,S T,疑問2：可不可以多向前走一些呢？ 主串往往很長(zhǎng)，不可能全部分析 因此只能

13、通過分析子串來分析主串 而目前最多知道T1.2匹配S4.5 并不能保證T1.匹配S5.,38,串的模式匹配：KMP算法,next函數(shù)的計(jì)算 一個(gè)遞歸的過程： 已知 next1=0 若 nextj=k 說明有 p1.pk-1=pj-k+1.pj-1 若pk=pj，則nextj+1=k+1 若pk!=pj，令k=nextk 若pk=pj，則nextj+1=k+1 若pk!=pj，則嘗試nextk.,39,串的模式匹配：KMP算法,分析 首先next1=0 假設(shè)已知nextj=k nextj+1=?,6,?,40,串的模式匹配：KMP算法,分析 若Tk=Tj 則nextj+1=k+1,7,41,串的

14、模式匹配：KMP算法,分析 若Tk!=Tj 令k=nextk 若Tk=Tj，則nextj+1=k+1,4,42,串的模式匹配：KMP算法,為什么令k=nextk？ next12=6，說明T1.5=T7.11 k=nextk=3，說明T1.2=T4.5 則T1.2=T10.11 若又有Tk=Tj，則nextj+1=k+1,4,43,串的模式匹配：KMP算法,匹配函數(shù),int Index_KMP(SString S, SString T, int pos) i = pos;j = 1; while(i T.curlen) return i-T.curlen; /匹配成功 else return 0

15、; /失敗 ,44,串的模式匹配：KMP算法,計(jì)算next的函數(shù),void get_next(SSTring T, int next) j = 1; next1 = 0;k = 0; while( j T.curlen ) if( k = 0 | Tj = Tk ) j+; k+; nextj = k; else k = nextk; /while ,45,KMP算法,next函數(shù)的不足,S T,46,S T,KMP算法,next函數(shù)的不足,通過對(duì)子串的分析可知T3=T4 如果現(xiàn)在T4和S5不匹配， 還需要再嘗試T3和S5么？,那就嘗試T3的下一個(gè)T2 結(jié)果T2=T3 因此嘗試T2的下一個(gè)T1

16、,結(jié)果T1=T2 T1的下一個(gè)next1=0 因此j=1; i+;,47,串的模式匹配：KMP算法,next函數(shù)的改進(jìn) 設(shè)k=nextj，其含義是當(dāng)Tj和Si不匹配時(shí)，嘗試Tk和Si 如果Tk=Tj，則不必嘗試Tk，而應(yīng)當(dāng)嘗試nextk 即nextj=nextk,48,改進(jìn)的next函數(shù),改進(jìn)的next函數(shù),void get_nextval(SSTring T, int next) j = 1;next1 = 0;k = 0; while( j T.curlen ) if( k = 0 | Tj = Tk ) j+; k+; if( Tj!=Tk ) nextj = k; else nextj = nextk; else k = nextk; /while ,49,改進(jìn)的next函數(shù),S T,50,KMP算法的另類應(yīng)用,問題： 有一個(gè)字符串，求其中最大的重復(fù)字串 比如：“abcabdabce” 結(jié)果是：abc,51,串的應(yīng)用,文本編輯的實(shí)質(zhì)就是利用串的基本操作，完成對(duì)文本的添加、刪除、修改和查找等操作。,看下面C程序： main(