字符串與模式匹配算法

字符串與模式匹配算法作業(yè)講評(píng)：鏈表應(yīng)用舉例

——Josephus問(wèn)題

求解Josephus問(wèn)題的一般步驟為：

（1）首先利用線性表的一些運(yùn)算如創(chuàng)建空線性表、插入元素等構(gòu)造Josephus表；

（2）從Josephus表中的第s個(gè)結(jié)點(diǎn)開(kāi)始尋找、輸出和刪除表中的第m個(gè)結(jié)點(diǎn)，然后再?gòu)脑摻Y(jié)點(diǎn)后的下一結(jié)點(diǎn)開(kāi)始尋找、輸出和刪除表中的第m個(gè)結(jié)點(diǎn)，重復(fù)此過(guò)程，直到Josephus表中的所有元素都刪除。

順序表應(yīng)用舉例——Josephus問(wèn)題voidjosephus_seq(PSeqListpalist,ints,intm){ints1,i,w;s1=s-1;for(i=palist->n;i>0;i--)/*找出列的元素*/{s1=(s1+m-1)%i;/*下一個(gè)出列的元素*/ w=palist->element[s1]; /*求下標(biāo)為s1的元素的值*/printf(“Outelement%d\n”,w); /*元素出列*/ delete_seq(palist,s1); /*刪除出列的元素*/ }}算法復(fù)雜度分析（順序結(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)算法復(fù)雜度分析（鏈表結(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)放在指針變量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))鏈表的用用：一元多項(xiàng)式和運(yùn)算一元多項(xiàng)式：Pn(x)=p0+p1x+p2x2+…+pnxn線性表表示：P=(p0,p1,p2,…,pn)順序表表示：只存系數(shù)（第i個(gè)元素存xi的系數(shù)）特殊問(wèn)題：p(x)=1+2x10000+4x40000鏈表表示：每個(gè)結(jié)點(diǎn)結(jié)構(gòu)系數(shù)指數(shù)0-110210000440000^一元多項(xiàng)式表示和運(yùn)算-3數(shù)據(jù)定義： typedefstruct{floatc;//系數(shù)inte;//指數(shù)

structitem*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)題）32519011010112263兩個(gè)一元多項(xiàng)式的乘法可以利用兩個(gè)一元多項(xiàng)式相加的算法來(lái)實(shí)現(xiàn)M(x)=A(x)B(x)=A(x)[b1xe1+b2xe2+...+bnxen]=O(n2)復(fù)雜度的運(yùn)算。字符串與模式匹配：字符串概念與抽象數(shù)據(jù)類型串模式匹配C語(yǔ)言中定義的字符串存儲(chǔ)結(jié)構(gòu)：字符指針…\0操作：<string.h>

char*strcpy(char*dst,char*sorc)intstrcmp(char*str1,char*str2);

char*strcat(char*dest,constchar*sorc,size);char*strstr(char*str,constchar*strSearch);size_tstrlen(constchar*str);gets(char*);puts(char*);串匹配函數(shù)：

char*strstr(constchar[],constchar[]);線性表到字符串ADTStringcreateNullStr(void)創(chuàng)建一個(gè)空串。intIsNullStr(Strings)判斷串s是否為空串，若為空串，則返回1，否則返回0。intlength(Strings)返回串s的長(zhǎng)度。Stringconcat(Strings1,Stings2)返回將串s1和s2拼接在一起構(gòu)成的一個(gè)新串。StringsubStr(Strings,inti,intj)在串s中，求從串的第i個(gè)字符開(kāi)始連續(xù)j個(gè)字符所構(gòu)成的子串。intindex(Strings1,Strings2)如果串s2是s1的子串，則可求串s2在串s1中第一次出現(xiàn)的位置。順序結(jié)構(gòu)字符串ADT的定義structSeqString{ /*順序串的類型*/intMAXNUM; /*串允許的最大字符個(gè)數(shù)*/intn; /*串的長(zhǎng)度，nMAXNUM*/char*c;};typedefstructSeqString*PSeqString;順序串示例s=“abcdefg”abcdefgs.n=7s.c0123456MAXNUM-1字符串ADT——?jiǎng)?chuàng)建順序結(jié)構(gòu)空串PSeqStringcreateNullStr_seq(intm){PSeqStringpstr=(PSeqString)malloc(sizeof(structSeqString)); if(pstr!=NULL){pstr->c=(char*)malloc(sizeof(char)*m);if(pstr->c！=NULL){pstr->n=0;pstr->MAXNUM=m;return(pstr)}elsefree(pstr);}printf("Outofspace!!\n");returnNULL;}structSeqString{ intMAXNUM;intn; char*c;};鏈接結(jié)構(gòu)字符串ADT的定義structStrNode; /*鏈串的結(jié)點(diǎn)*/ typedefstructStrNode*PStrNode;/*結(jié)點(diǎn)指針類型*/ structStrNode{ /*鏈串的結(jié)點(diǎn)結(jié)構(gòu)*/ charc; PStrNodelink; }; typedefstructStrNode*LinkString; /*鏈串的類型*/字符串結(jié)尾？長(zhǎng)度？字符串的鏈接存儲(chǔ)示例sabcd^sabcd^不帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn)abcds帶尾指針的循環(huán)鏈表鏈接存儲(chǔ)字符串的基本運(yùn)算創(chuàng)建空鏈串聯(lián)結(jié)兩個(gè)串取單鏈串的子串刪除子串追加方式插入子串子串定位[模式匹配]求串長(zhǎng)創(chuàng)建帶頭結(jié)點(diǎn)的空鏈串LinkStringcreateNullStr_link(void){ LinkStringpst; pst=(LinkString)malloc(sizeof(structStrNode)); if(pst!=NULL) pst->link=NULL; else printf("Outofspace!\n");/*創(chuàng)建失敗*/ return(pst);}串模式匹配問(wèn)題設(shè)有兩個(gè)串t和p:t=t0t1…tn-1，p=p0p1…pm-1

其中1<m<=n(通常m<<n)模式匹配的目的是在t中找出和p相同的子串。此時(shí)，t稱為“目標(biāo)”，而p稱為“模式”。模式匹配的結(jié)果有兩種：匹配成功：t中存在等于p的子串，返回子串在t中的位置匹配失?。悍祷匾粋€(gè)特定的標(biāo)志（如-1）。兩種模式匹配方法模式匹配是一個(gè)比較復(fù)雜的字符串操作，下面的討論是基于字符串的順序存儲(chǔ)結(jié)構(gòu)進(jìn)行。分為樸素的模式匹配方法和無(wú)回溯的模式匹配方法匹配思想匹配示例匹配算法算法時(shí)間效率分析樸素的模式匹配思想

p中字符依次與t中字符一一比較：t0t1…tjtj+1…tj+m-1…tn

p0p1…pm-1

如果對(duì)于所有的i(0<=i<=m-1),皆有tj+i=pi，則匹配成功，返回位置j；否則，此趟匹配失敗，這時(shí)將p右移一個(gè)字符，進(jìn)行下一趟匹配：t0t1…tjtj+1tj+2…tj+m…tn

p0p1…pm-1

直到匹配成功或p移動(dòng)到無(wú)法與t繼續(xù)比較為止（匹配失敗）。樸素的模式匹配——匹配子串intindex(PSeqStringt,PSeqStringp)求p所指的串在t所指的串中第一次出現(xiàn)時(shí)，p所指串的第一個(gè)元素在t所指的串中的序號(hào)(下標(biāo)+1)。

算法：用p中的字符依次與t中的字符比較，如果：t0=p0，t1=p1，…，tm-1=pm-1，則匹配成功，返回字符t0的位置。否則：t0++;從p0開(kāi)始新一輪比較。直到：匹配成功?；颍簊trlen(p)>strlen(t0);樸素子串匹配法示例（每次p右移一個(gè)單元）

算法時(shí)間效率分析匹配失敗的最壞情況：每趟匹配皆在最后一個(gè)字符不等，且有n-m+1趟匹配(每趟比較m個(gè)字符），共比較m*(n-m+1)次，由于m<<n，因此最壞時(shí)間復(fù)雜度O(n*m)。匹配失敗的最好情況：n-m+1次比較[每趟只比較第一個(gè)字符]。匹配成功的最好情況：m次比較。匹配成功的最壞情況：與匹配失敗的最壞情況相同。綜上討論：樸素模式匹配算法的時(shí)間復(fù)雜度為O(m*n)無(wú)回溯的模式匹配方法(KMP算法)利用已經(jīng)匹配過(guò)子串的歷史信息來(lái)指導(dǎo)下一步匹配的方案。模式串的特征數(shù)與特征向量模式串P開(kāi)頭的任意個(gè)字符，把它稱為前綴子串。p0p1p2…pm-1在P的第i位置的左邊，取出k個(gè)字符，稱為i位置的左子串。pi-k+1...pi-2pi-1pi求出最長(zhǎng)的（最大的k）使得前綴子串與左子串相匹配稱為，在第i位的最長(zhǎng)前綴串。第i位的最長(zhǎng)前綴串的長(zhǎng)度k就是模板串P在位置i上的特征數(shù)n[i]特征數(shù)組成的向量稱為該模式串的特征向量。KMP算法基本思想第i個(gè)位置的特征值k僅依賴于模式p本身前i個(gè)字符的組成，而與目標(biāo)t無(wú)關(guān)，一般可用next[i]表示與i對(duì)應(yīng)的k值。若next[i]≥0，表示一旦匹配過(guò)程中pi與tj比較不等，可用p中以next[i]為下標(biāo)的字符與tj進(jìn)行比較。next[i]==-1?對(duì)于任意模式p，只要我們能夠確定next[i](i=0,1,…,m-1)的值，就可以加速匹配過(guò)程，避免回溯問(wèn)題。當(dāng)tj≠pi時(shí)，模式串回溯（右移）i-next[i]個(gè)字符，從目標(biāo)串tj位置繼續(xù)下去。Next數(shù)組（特征向量）的計(jì)算在p與任意的目標(biāo)串t匹配時(shí)，若發(fā)現(xiàn)tj≠pi，則意味著p0、p1、…、pi-1已經(jīng)與t中對(duì)應(yīng)的字符進(jìn)行過(guò)比較，而且是相等的，否則輪不到tj與pi的比較，因此下面兩個(gè)圖是等價(jià)的