字符串與模式匹配算法

1、字符串與模式匹配算法 2010/03/142用數(shù)組來(lái)實(shí)現(xiàn)鏈表結(jié)構(gòu)用數(shù)組來(lái)實(shí)現(xiàn)鏈表結(jié)構(gòu) struct Node DataType num; int next ; struct Slinklist Node listMAXNUM; int elementNum; 1290-1634-11234作業(yè)講評(píng)：作業(yè)講評(píng)：56789101112鏈表應(yīng)用舉例鏈表應(yīng)用舉例 Josephus問(wèn)題問(wèn)題 求解Josephus問(wèn)題的一般步驟為：（1）首先利用線(xiàn)性表的一些運(yùn)算如創(chuàng)建空線(xiàn)性表、插入元素等構(gòu)造Josephus表；（2）從Josephus表中的第s個(gè)結(jié)點(diǎn)開(kāi)始尋找、輸出和刪除表中的第m個(gè)結(jié)點(diǎn)，然后再?gòu)脑摻Y(jié)點(diǎn)后的下

2、一結(jié)點(diǎn)開(kāi)始尋找、輸出和刪除表中的第m個(gè)結(jié)點(diǎn)，重復(fù)此過(guò)程，直到Josephus表中的所有元素都刪除。13順序表應(yīng)用舉例順序表應(yīng)用舉例 Josephus問(wèn)題問(wèn)題void josephus_seq( PSeqList palist, int s, int m) int s1, i, w; s1 = s - 1; for( i = palist-n; i0; i-) /* 找出列的元素 */ s1 = ( s1 + m - 1 ) % i ; /*下一個(gè)出列的元素*/ w = palist-elements1; /* 求下標(biāo)為s1的元素的值 */ printf(“Out element %d n”,w

3、); /* 元素出列 */ delete_seq(palist,s1); /* 刪除出列的元素 */14算法復(fù)雜度分析算法復(fù)雜度分析 （順序結(jié)構(gòu)）（順序結(jié)構(gòu)） 步驟： 1: 建立順序表 2: 出列 時(shí)間復(fù)雜度分析：出列元素的刪除（移動(dòng)實(shí)現(xiàn)）為基本運(yùn)算（每次最多i-1個(gè)元素移動(dòng)，需要n-1次） (n-1)+(n-2)+1 = n(n-1)/2 = O(n2)15算法復(fù)雜度分析算法復(fù)雜度分析 （鏈表結(jié)構(gòu)）（鏈表結(jié)構(gòu)）步驟：(1)建立循環(huán)鏈表；(2)找循環(huán)單鏈表中的第s個(gè)結(jié)點(diǎn)放在指針變量p中(3)從p所指結(jié)點(diǎn)開(kāi)始計(jì)數(shù)尋找第m個(gè)結(jié)點(diǎn)，輸出該結(jié)點(diǎn)的元素值； (4)刪除該結(jié)點(diǎn)，并將該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)放在指

4、針變量p中，轉(zhuǎn)去執(zhí)行(2)，直到所有結(jié)點(diǎn)被刪除為止；時(shí)間復(fù)雜度分析：三部分時(shí)間（創(chuàng)建鏈表：O(n)+ 求第s個(gè)結(jié)點(diǎn)：O(s)+ 求n個(gè)第m個(gè)應(yīng)出列的元素：O(m*n)16鏈表的用用：鏈表的用用：一元多項(xiàng)式和運(yùn)算一元多項(xiàng)式和運(yùn)算一元多項(xiàng)式：一元多項(xiàng)式：P Pn n(x(x) = p) = p0 0+p+p1 1x+px+p2 2x x2 2+p pn n x xn n線(xiàn)性表表示：線(xiàn)性表表示：P=(pP=(p0 0, p, p1 1, p, p2 2, , , , p pn n) )順序表表示：順序表表示：只存系數(shù)（第只存系數(shù)（第i i個(gè)元素存?zhèn)€元素存x xi i的系數(shù)）的系數(shù)） 特殊問(wèn)題：特殊問(wèn)

5、題：p(xp(x) = 1+ 2x) = 1+ 2x10000 10000 + 4x+ 4x4000040000鏈表表示：鏈表表示： 每個(gè)結(jié)點(diǎn)結(jié)構(gòu)每個(gè)結(jié)點(diǎn)結(jié)構(gòu)系數(shù) 指數(shù)0 -11021000044000017一元多項(xiàng)式表示和運(yùn)算一元多項(xiàng)式表示和運(yùn)算-3數(shù)據(jù)定義：typedef struct float c; /系數(shù) int e; /指數(shù) struct item *next Item ;加法: 相同指數(shù)對(duì)應(yīng)結(jié)點(diǎn)的系數(shù)項(xiàng)相加， 如和為0，刪除結(jié)點(diǎn)，否則必定為 和鏈表的一個(gè)結(jié)點(diǎn)。 （實(shí)質(zhì)上就是兩個(gè)單鏈表的合并問(wèn)題）3251901101011226318兩個(gè)一元多項(xiàng)式的乘法兩個(gè)一元多項(xiàng)式的乘法 可以利

6、用兩個(gè)一元多項(xiàng)式相加的算法來(lái)實(shí)現(xiàn) M(x) = A(x) B(x)= A(x) b1xe1+b2xe2+.+bnxen=nieiixxAb1)(O(n2)復(fù)雜度的運(yùn)算。19字符串與模式匹配：字符串與模式匹配： 字符串概念與抽象數(shù)據(jù)類(lèi)型 串模式匹配20C語(yǔ)言中定義的字符串語(yǔ)言中定義的字符串 存儲(chǔ)結(jié)構(gòu)： 字符指針 0 操作： char *strcpy(char *dst, char *sorc) int strcmp(char *str1, char *str2); char* strcat(char *dest, const char* sorc,size); char* strstr(char

7、 *str, const char *strSearch); size_t strlen(const char* str); gets(char *); puts(char*); 21串匹配函數(shù)：串匹配函數(shù)： char* strstr(const char ,constchar );22線(xiàn)性表到字符串線(xiàn)性表到字符串ADTString createNullStr (void) 創(chuàng)建一個(gè)空串。int IsNullStr ( String s ) 判斷串s是否為空串，若為空串，則返回1，否則返回0。int length ( String s ) 返回串s的長(zhǎng)度。String concat (Stri

8、ng s1, Sting s2 ) 返回將串s1和s2拼接在一起構(gòu)成的一個(gè)新串。String subStr (String s, int i, int j ) 在串s中，求從串的第i個(gè)字符開(kāi)始連續(xù)j個(gè)字符所構(gòu)成的子串。int index (String s1, String s2 ) 如果串s2是s1的子串，則可求串s2在串s1中第一次出現(xiàn)的位置。23順序結(jié)構(gòu)順序結(jié)構(gòu)字符串字符串ADT的的定義定義struct SeqString /* 順序串的類(lèi)型 */ int MAXNUM; /* 串允許的最大字符個(gè)數(shù) */ int n; /* 串的長(zhǎng)度，nMAXNUM */ char *c;typedef

9、 struct SeqString *PSeqString;24順序串示例順序串示例 s = “abcdefg”a b c d efgs.n = 7s.c 0 1 2 3 4 5 6 MAXNUM-125字符串字符串ADT 創(chuàng)建順序結(jié)構(gòu)空串創(chuàng)建順序結(jié)構(gòu)空串PSeqString createNullStr_seq( int m ) PSeqString pstr = (PSeqString)malloc(sizeof(struct SeqString); if (pstr != NULL) pstr-c = (char* )malloc(sizeof (char)*m); if (pstr-c

10、！= NULL) pstr-n = 0; pstr-MAXNUM = m; return (pstr) else free (pstr); printf(Out of space!n); return NULL;struct SeqString int MAXNUM; int n; char *c;26鏈接結(jié)構(gòu)鏈接結(jié)構(gòu)字符串字符串ADT的的定義定義struct StrNode; /* 鏈串的結(jié)點(diǎn) */typedef struct StrNode *PStrNode; /* 結(jié)點(diǎn)指針類(lèi)型 */struct StrNode /* 鏈串的結(jié)點(diǎn)結(jié)構(gòu) */char c;PStrNode link; ;t

11、ypedef struct StrNode *LinkString; /* 鏈串的類(lèi)型 */字符串結(jié)尾？長(zhǎng)度？27字符串的鏈接存儲(chǔ)示例字符串的鏈接存儲(chǔ)示例sabcdsabcd不帶頭結(jié)點(diǎn)不帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn)abcds帶尾指針的循環(huán)鏈表帶尾指針的循環(huán)鏈表28鏈接存儲(chǔ)字符串的基本運(yùn)算鏈接存儲(chǔ)字符串的基本運(yùn)算 創(chuàng)建空鏈串 聯(lián)結(jié)兩個(gè)串 取單鏈串的子串取單鏈串的子串 刪除子串 追加方式插入子串追加方式插入子串 子串定位 模式匹配 求串長(zhǎng)29創(chuàng)建帶頭結(jié)點(diǎn)的空鏈串創(chuàng)建帶頭結(jié)點(diǎn)的空鏈串LinkString createNullStr_link( void ) LinkString pst;pst = (L

12、inkString)malloc( sizeof(struct StrNode) );if (pst!=NULL)pst-link = NULL;else printf(Out of space! n); /*創(chuàng)建失敗*/ return (pst);30串模式匹配問(wèn)題串模式匹配問(wèn)題 設(shè)有兩個(gè)串 t和p : t = t0t1tn-1，p = p0p1p m-1 其中 1m=n(通常 mn) 模式匹配的目的是在t中找出和p相同的子串。 此時(shí)，t稱(chēng)為“目標(biāo)”，而p稱(chēng)為“模式”。 模式匹配的結(jié)果有兩種： 匹配成功：t中存在等于p的子串，返回子串在t中的位置 匹配失?。悍祷匾粋€(gè)特定的標(biāo)志（如-1）。31

13、兩種模式匹配方法兩種模式匹配方法 模式匹配是一個(gè)比較復(fù)雜的字符串操作，下面的討論是基于字符串的順序存儲(chǔ)順序存儲(chǔ)結(jié)構(gòu)進(jìn)行。分為樸素的模式匹配方法和無(wú)回溯的模式匹配方法 匹配思想 匹配示例 匹配算法 算法時(shí)間效率分析32樸素的模式匹配思想樸素的模式匹配思想 p p中字符依次與中字符依次與t t中字符一一比較：中字符一一比較： t t0 0 t t1 1 t tj j t tj+1j+1 t tj+m-1j+m-1 t tn n p p0 0 p p1 1 p pm-1m-1 如果對(duì)于所有的如果對(duì)于所有的i i( 0=i=m-1)( 0=istrlen(t0);34樸素子串匹配法示例（樸素子串匹配法

14、示例（每次每次p右移一個(gè)單元）右移一個(gè)單元） 下標(biāo)j01234567891011121314151617目標(biāo)taabcbabcaabcaababc模式pabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababcabcaababc3536算法時(shí)間效率分析算法時(shí)間效率分析 匹配失敗的最壞情況：每趟匹配皆在最后一個(gè)字符不等，且有n-m+1趟匹配(每趟比較m個(gè)字符），共比較m*(n-m+1)次，由于mn，因此最壞時(shí)間復(fù)雜度O(n*m)。 匹配失敗的最好情況：n-m+1次比較每趟只比較第一個(gè)字符。 匹

15、配成功的最好情況：m次比較。 匹配成功的最壞情況：與匹配失敗的最壞情況相同。 綜上討論：樸素模式匹配算法的時(shí)間復(fù)雜度為O(m*n)37無(wú)回溯的模式匹配方法無(wú)回溯的模式匹配方法(KMP算法算法) 利用已經(jīng)匹配過(guò)子串的歷史信息來(lái)指導(dǎo)下一步匹配的方案。38模式串的特征數(shù)與特征向量模式串的特征數(shù)與特征向量 模式串P開(kāi)頭的任意個(gè)字符，把它稱(chēng)為前綴子串。p0p1p2pm-1 在P的第i位置的左邊，取出k個(gè)字符，稱(chēng)為i位置的左子串。pi-k+1. pi-2 pi-1 pi 求出最長(zhǎng)的（最大的k）使得前綴子串與左子串相匹配稱(chēng)為，在第i位的最長(zhǎng)前綴串。 第i位的最長(zhǎng)前綴串的長(zhǎng)度k就是模板串P在位置i上的特征特征

16、數(shù)數(shù)ni 特征數(shù)組成的向量稱(chēng)為該模式串的特征向量特征向量。39KMP算法基本思想算法基本思想第i個(gè)位置的特征值k 僅依賴(lài)于模式p本身前i個(gè)字符的組成，而與目標(biāo)t無(wú)關(guān)，一般可用nexti表示與i對(duì)應(yīng)的k值。 若nexti0，表示一旦匹配過(guò)程中pi與tj比較不等，可用p中以nexti為下標(biāo)的字符與tj進(jìn)行比較。 nexti = -1?對(duì)于任意模式p，只要我們能夠確定 nexti (i=0, 1, , m-1)的值，就可以加速匹配過(guò)程，避免回溯問(wèn)題。當(dāng)tj pi時(shí)，模式串回溯（右移） i-nexti個(gè)字符，從目標(biāo)串 tj位置繼續(xù)下去。40Next數(shù)組（特征向量）的計(jì)算數(shù)組（特征向量）的計(jì)算 在p與任意的目標(biāo)串t匹配時(shí)，若發(fā)現(xiàn)tjpi，則意味著p0、p1、pi-1已經(jīng)與t中對(duì)應(yīng)的字符進(jìn)行過(guò)比較，而且是相等的，否則輪不到tj與pi