1、4.1 串類型的定義串類型的定義4.2 串的表示和實現(xiàn)串的表示和實現(xiàn)4.3 串的模式匹配算法串的模式匹配算法設(shè)有兩個字符串設(shè)有兩個字符串S S1 1和和S S2 2：S S1 1 =adbcgsdbcdf =adbcgsdbcdfS S2 2 =dbc =dbc 空串是任意串的子串 任意串S都是S本身的子串 真子串：非空且不為自身的子串 設(shè)有兩個字符串設(shè)有兩個字符串S S1 1和和S S2 2：S S1 1 =adbcgsdbcdf =adbcgsdbcdfS S2 2 =dbc =dbc 線性表的大多以元素為操作對象 串通常以整個串作為操作對象 線性表的存儲方法同樣適用于字符串 ADT St

2、ring 數(shù)據(jù)對象：數(shù)據(jù)對象：D=ai| aiCharacterSet； i=1,2,n,；n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1=| ai-1, aiD； i= 2,n 基本操作：基本操作： 初始條件：初始條件：chars是字符串常量。是字符串常量。 操作結(jié)果：生成一個其值等于操作結(jié)果：生成一個其值等于chars的串的串T。 初始條件：串初始條件：串S存在。存在。 操作結(jié)果：由串操作結(jié)果：由串S復(fù)制得串復(fù)制得串T。 初始條件：串初始條件：串S存在。存在。 操作結(jié)果：若操作結(jié)果：若S為空串，則返回為空串，則返回TRUE，否則返回，否則返回FALSE。 初始條件：串初始條件：串S存在。存在。 操作結(jié)果：

3、則返操作結(jié)果：則返S的元素個數(shù)，稱為串的長度。的元素個數(shù)，稱為串的長度。 初始條件：串初始條件：串S和和T存在。存在。 操作結(jié)果操作結(jié)果:若若ST，則返回值，則返回值0；若；若S = T，則返回值，則返回值=0；若；若ST，則返回值，則返回值0) n= StrLength(S); m= StrLength (T); i= pos; while( i= n-m+1) SubString (sub, S, i, m); if (StrCompare(sub, T)!=0) +i; else return i; /返回子串在主串中的位置返回子串在主串中的位置 /while / if return 0

4、; /S中不存在與中不存在與T相等的子串相等的子串/Index一、定長順序存儲一、定長順序存儲為每個串分配一個固定長度的存儲區(qū)為每個串分配一個固定長度的存儲區(qū) 用一組地址連續(xù)的存儲單元存儲串用一組地址連續(xù)的存儲單元存儲串 #define MAXSTRLEN 255 typedef unsigned char SStringMAXSTRLEN + 1 lPASCAL方式lC方式8 a b c d e f g ha b c d e f g h 0二、二、 采用采用C方式和動態(tài)存儲分配方式和動態(tài)存儲分配typedef structchar *ch; /若是非空串，則按串長分配存儲區(qū)若是非空串，則按串

5、長分配存儲區(qū),否則否則ch為為NULL int length; /串長度串長度HString;三、三、塊鏈存儲塊鏈存儲/= = = = = =串的存儲表示串的存儲表示= = = = = = #define CHUNKSIZE 80 /可由用戶定義的塊大小可由用戶定義的塊大小typedef struct Chunk char chCHUNKSIZE; struct Chunk *next; Chunk;typedef struct Chunk *head, *tail; /串的頭和尾指針串的頭和尾指針 int curlen; /串的當(dāng)前長度串的當(dāng)前長度LString實際分配的存儲位串值所占的存儲

6、位存儲密度 4.3 串的模式匹配算法串的模式匹配算法在主串S中尋找子串T的過程稱為模式匹配模式匹配 S為目標(biāo)串，T稱為模式串模式匹配模式匹配 精確匹配精確匹配 近似匹配近似匹配 匹配結(jié)果匹配結(jié)果 匹配成功匹配成功 匹配不成功匹配不成功 應(yīng)用：應(yīng)用： 文本編輯時的特定詞、句的查找文本編輯時的特定詞、句的查找 DNA信息的提取信息的提取模式匹配模式匹配( (采用PASCAL方式存儲) ) S1 Si Si+1 Si+2 Si+m-2 Si+m-1 Sn p1 p2 p3 pm -1 pmS:T:為使模式為使模式S S與目標(biāo)與目標(biāo)T T 匹配，必須滿足匹配，必須滿足 p1 p2 pm = Si Si

7、+1 Si+m-1模式匹配算法（窮舉法，樸素算法）模式匹配算法（窮舉法，樸素算法）S1S2S3S4. Sm-1Sm.Snp1p2p3p4. pm-1pm從頭開始匹配從頭開始匹配假設(shè)pos=1STS1S2S3S4. Sm-1Sm. Snp1p2p3p4. pm-1pm若若Sipj 回溯回溯模式右滑一位模式右滑一位再匹配再匹配ST主串S模式T j回回溯溯回回溯溯本 趟 匹 配開始位置iabacababacaacabcabacabaaaabaabacaabacabab181234587691011121314151617主串S模式T Si-j+1 . Si-1Si.Snp1p2.pjSTSi-j+j

8、Si-j+1當(dāng)當(dāng)Si-j+1=p1 Si-j+2=p2 Si-j+j-1=pj-1 Si-j+jpj時時回溯：比較回溯：比較Si-j+2與與p1是否相等是否相等int Index(SString S, SString T, int pos) /返回子串返回子串T在主串在主串S中第中第pos 個字符之后的位置個字符之后的位置 /若不存在，函數(shù)值為若不存在，函數(shù)值為0 /T為非空串，為非空串，1posStrLength (S) i=pos; j=1; while(i=S0&jT0) return i-T0; else return 0; /index 算法分析：算法分析：aaaaaaaaa

9、aaaaaaaaaaaaaab181234587691011121314151617匹配成功的最佳實例，O(m)bbacaa匹配不成功的最佳實例，O(n-m)aaaaab匹配成功的最差實例，O(nm)思考：當(dāng)當(dāng)Sipj 時，之前已經(jīng)比較過時，之前已經(jīng)比較過j-1對字符，對字符，這些比較結(jié)果是否可以利用？這些比較結(jié)果是否可以利用？主串S模式T:abacababacaacabcabacabaaaab當(dāng)當(dāng)S6p6時，模式右滑一位，時，模式右滑一位，比較比較S2和和p1之前之前S2與與p2已經(jīng)比較過已經(jīng)比較過，p2=S2,而而p2p1,所以S2 p1,不需要比較不需要比較只需要比較只需要比較S4和和p

10、21812345876910111213141516 17主串S模式TS S1 Si-j-1 Si-j Si-j+1 Si-j+2 Si Si-1 Si Sn T p1 p2 pj pj -1 pj Si-j+1 Si-j+2 Si-1 = p1 p2 pj-1 p1 p2 pj-2 p2 p3 pj-1 p1 p2 pj-2 Si-j+2 Si-j+3 Si-1 下一趟一定不匹配下一趟一定不匹配在模式T與目標(biāo)S的匹配過程中,當(dāng)某次比較出現(xiàn): Si pj之前的比較有:p1.j-1=Si-j+1.i-1 共j-1對字符相等如果:(1)p1.j-2=p2.j-1,則p1.j-2=Si-j+2.i-

11、1 模式右移一位后,前j-2對字符必相等, 只需要比較pj-1與Si否相等,指針i不需要回溯i-j+1 i-1 iS1 j-1 jTi-j+1 i-1 iS1 j-1T否則(2)p1.j-3=p3.j-1,則p1.j-3=Si-j+3.i-1 模式右移兩位后,前j-3對字符必相等, 只需要比較pj-2與Si否相等,指針i不需要回溯i-j+1 i-1 iS1 j-1 jTi-j+1 i-1 iS1 j-2T依次類推,如果可以找到一個最大的k,有p1.k-1=pj-k+1.j-1, 則p1.k-1=Si-k+1.i-1 模式右移j-k位后,前k-1對字符必相等, 只需要比較pk與Si是是否相等,指

12、針i不需要回溯i-j+1 i-1 iS1 j-1 jTi-k+1 i-1 iS1 kTSTijk-1kSiTk-1k的大小與的大小與T、j的值有關(guān)，與的值有關(guān)，與S無關(guān)無關(guān)| | | | 在匹配的過程中,出現(xiàn)Sipj時, 滿足條件p1.k-1=pj-k+1.j-1的k值與模式串、j有關(guān), 與目標(biāo)串無關(guān)(kj)找到k值的作用： 當(dāng)出現(xiàn)失配時, Si 應(yīng)與模式中的哪個字符比較?與pj有關(guān)的k值稱為特征數(shù)，所有的特征數(shù)用數(shù)組next記錄。nextj=0 j=1時maxk|1k0,令k=nextj，如何計算nextj+1若pj=pkTj-k+1 j-11 k-1Tj-k+1 j-1 j1 k-1 kn

13、extj+1=k+1;.Si-jSi-j+1Si-j+2Si-k+2. Si-kSi-k+1.Si.p1p2pj-kpj-k+1. pj-2pj-1p1p2pk. pk-2pk-1Si-2Si-1pj-k+2pj| | | | | | | | | |如果j0,令k=nextj，若pj pk 又是一個模式匹配問題，模式串既是目標(biāo)又是模式 模式右移（滑動）第nextk個字符與pj比較 若nextk=h且ph=pj,則ph+1與Si比較 （p1.h=pj-h+1.j，nextj+1=h+1） 若ph pj，模式繼續(xù)右移 直到pj與模式中的某個字符匹配成功或找不到任何h nextj+1=1;Tjnex

14、tj=kk-1Tj若若pkpj,設(shè)設(shè)nextk=hk-1nextj+1=h+1=nextk+1Tj若若pnextk =pjk-1h-1jnext1 02 13 14 15 16 27 28 39 410 2例：例：T=abcdaabcabvoid get_next(SString T,int next) /求模式串T的next函數(shù)值并存如數(shù)組next j=1; nextj=0; k=0; while(jT0) if(k=0|Tj=Tk) +j; +k; nextj=k; else k=nextk; /get_next int Index_KMP(SString S,SString T,int

15、pos) /利用模式T的 next函數(shù)求T在主串S中第pos個字符后的位置 /的 KMP算法，其中T非空， 1posStrLength(S) i=pos; j=1; while(i=S0&jT0) return i-T0; else return 0;/Index_KMP 由于指針由于指針i i無須回溯，比較次數(shù)僅為無須回溯，比較次數(shù)僅為n,n,即使加上計算即使加上計算nextjnextj時所用的比較次數(shù)時所用的比較次數(shù)m m，比較總次數(shù)也僅為，比較總次數(shù)也僅為n+m=n+m=O(nm)，大大大快于窮舉算法。大快于窮舉算法。a b aca acabca b aca b a aa b a

16、ca b1 2 3 4 5 6a b acab7a b aca b8 9 10 11 12a b aca b13a b aca b14 15 16 17 18 19212110NextbacabaP654321ja a a a b aaaaa a a a a a ba a a a a b1 2 3 4 56a a a a ab543210NextbaaaaaP654321ja a a a a b7a a a a a b8a a a a a b9.Si-jSi-j+1Si-j+2Si-k+2. Si-kSi-k+1.Sip1p2pj-kpj-k+1. pj-2pj-1p1p2pk. pk-2pk-1Si-2Si-1pj-k+2pj| | | | | | | | |