字符串與模式匹配算法

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

2、一結(jié)點開始尋找、輸出和刪除表中的第m個結(jié)點，重復(fù)此過程，直到Josephus表中的所有元素都刪除。13順序表應(yīng)用舉例順序表應(yīng)用舉例 Josephus問題問題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 ; /*下一個出列的元素*/ w = palist-elements1; /* 求下標為s1的元素的值 */ printf(“Out element %d n”,w

3、); /* 元素出列 */ delete_seq(palist,s1); /* 刪除出列的元素 */14算法復(fù)雜度分析算法復(fù)雜度分析 （順序結(jié)構(gòu)）（順序結(jié)構(gòu)） 步驟： 1: 建立順序表 2: 出列 時間復(fù)雜度分析：出列元素的刪除（移動實現(xiàn)）為基本運算（每次最多i-1個元素移動，需要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個結(jié)點放在指針變量p中(3)從p所指結(jié)點開始計數(shù)尋找第m個結(jié)點，輸出該結(jié)點的元素值； (4)刪除該結(jié)點，并將該結(jié)點的下一個結(jié)點放在指

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

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

6、用兩個一元多項式相加的算法來實現(xiàn) M(x) = A(x) B(x)= A(x) b1xe1+b2xe2+.+bnxen=nieiixxAb1)(O(n2)復(fù)雜度的運算。19字符串與模式匹配：字符串與模式匹配： 字符串概念與抽象數(shù)據(jù)類型 串模式匹配20C語言中定義的字符串語言中定義的字符串 存儲結(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線性表到字符串線性表到字符串ADTString createNullStr (void) 創(chuàng)建一個空串。int IsNullStr ( String s ) 判斷串s是否為空串，若為空串，則返回1，否則返回0。int length ( String s ) 返回串s的長度。String concat (Stri

8、ng s1, Sting s2 ) 返回將串s1和s2拼接在一起構(gòu)成的一個新串。String subStr (String s, int i, int j ) 在串s中，求從串的第i個字符開始連續(xù)j個字符所構(gòu)成的子串。int index (String s1, String s2 ) 如果串s2是s1的子串，則可求串s2在串s1中第一次出現(xiàn)的位置。23順序結(jié)構(gòu)順序結(jié)構(gòu)字符串字符串ADT的的定義定義struct SeqString /* 順序串的類型 */ int MAXNUM; /* 串允許的最大字符個數(shù) */ int n; /* 串的長度，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é)點 */typedef struct StrNode *PStrNode; /* 結(jié)點指針類型 */struct StrNode /* 鏈串的結(jié)點結(jié)構(gòu) */char c;PStrNode link; ;t

11、ypedef struct StrNode *LinkString; /* 鏈串的類型 */字符串結(jié)尾？長度？27字符串的鏈接存儲示例字符串的鏈接存儲示例sabcdsabcd不帶頭結(jié)點不帶頭結(jié)點帶頭結(jié)點帶頭結(jié)點abcds帶尾指針的循環(huán)鏈表帶尾指針的循環(huán)鏈表28鏈接存儲字符串的基本運算鏈接存儲字符串的基本運算 創(chuàng)建空鏈串 聯(lián)結(jié)兩個串 取單鏈串的子串取單鏈串的子串 刪除子串 追加方式插入子串追加方式插入子串 子串定位 模式匹配 求串長29創(chuàng)建帶頭結(jié)點的空鏈串創(chuàng)建帶頭結(jié)點的空鏈串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串模式匹配問題串模式匹配問題 設(shè)有兩個串 t和p : t = t0t1tn-1，p = p0p1p m-1 其中 1m=n(通常 mn) 模式匹配的目的是在t中找出和p相同的子串。 此時，t稱為“目標”，而p稱為“模式”。 模式匹配的結(jié)果有兩種： 匹配成功：t中存在等于p的子串，返回子串在t中的位置 匹配失?。悍祷匾粋€特定的標志（如-1）。31

13、兩種模式匹配方法兩種模式匹配方法 模式匹配是一個比較復(fù)雜的字符串操作，下面的討論是基于字符串的順序存儲順序存儲結(jié)構(gòu)進行。分為樸素的模式匹配方法和無回溯的模式匹配方法 匹配思想 匹配示例 匹配算法 算法時間效率分析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 如果對于所有的如果對于所有的i i( 0=i=m-1)( 0=istrlen(t0);34樸素子串匹配法示例（樸素子串匹配法

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

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

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