字符串與模式匹配算法

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

——Josephus問題

求解Josephus問題的一般步驟為：

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

（2）從Josephus表中的第s個結(jié)點開始尋找、輸出和刪除表中的第m個結(jié)點，然后再從該結(jié)點后的下一結(jié)點開始尋找、輸出和刪除表中的第m個結(jié)點，重復此過程，直到Josephus表中的所有元素都刪除。

順序表應(yīng)用舉例——Josephus問題voidjosephus_seq(PSeqListpalist,ints,intm){ints1,i,w;s1=s-1;for(i=palist->n;i>0;i--)/*找出列的元素*/{s1=(s1+m-1)%i;/*下一個出列的元素*/ w=palist->element[s1]; /*求下標為s1的元素的值*/printf(“Outelement%d\n”,w); /*元素出列*/ delete_seq(palist,s1); /*刪除出列的元素*/ }}算法復雜度分析（順序結(jié)構(gòu)）步驟：1:建立順序表2:出列時間復雜度分析：出列元素的刪除（移動實現(xiàn)）為基本運算（每次最多i-1個元素移動，需要n-1次）(n-1)+(n-2)+……+1=n(n-1)/2=>O(n2)算法復雜度分析（鏈表結(jié)構(gòu)）步驟：(1)建立循環(huán)鏈表；(2)找循環(huán)單鏈表中的第s個結(jié)點放在指針變量p中(3)從p所指結(jié)點開始計數(shù)尋找第m個結(jié)點，輸出該結(jié)點的元素值；(4)刪除該結(jié)點，并將該結(jié)點的下一個結(jié)點放在指針變量p中，轉(zhuǎn)去執(zhí)行(2)，直到所有結(jié)點被刪除為止；時間復雜度分析：三部分時間（創(chuàng)建鏈表：O(n)+求第s個結(jié)點：O(s)+求n個第m個應(yīng)出列的元素：O(m*n))鏈表的用用：一元多項式和運算一元多項式：Pn(x)=p0+p1x+p2x2+…+pnxn線性表表示：P=(p0,p1,p2,…,pn)順序表表示：只存系數(shù)（第i個元素存xi的系數(shù)）特殊問題：p(x)=1+2x10000+4x40000鏈表表示：每個結(jié)點結(jié)構(gòu)系數(shù)指數(shù)0-110210000440000^一元多項式表示和運算-3數(shù)據(jù)定義： typedefstruct{floatc;//系數(shù)inte;//指數(shù)

structitem*next}Item;加法:相同指數(shù)對應(yīng)結(jié)點的系數(shù)項相加，如和為0，刪除結(jié)點，否則必定為和鏈表的一個結(jié)點。（實質(zhì)上就是兩個單鏈表的合并問題）32519011010112263兩個一元多項式的乘法可以利用兩個一元多項式相加的算法來實現(xiàn)M(x)=A(x)B(x)=A(x)[b1xe1+b2xe2+...+bnxen]=O(n2)復雜度的運算。字符串與模式匹配：字符串概念與抽象數(shù)據(jù)類型串模式匹配C語言中定義的字符串存儲結(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)建一個空串。intIsNullStr(Strings)判斷串s是否為空串，若為空串，則返回1，否則返回0。intlength(Strings)返回串s的長度。Stringconcat(Strings1,Stings2)返回將串s1和s2拼接在一起構(gòu)成的一個新串。StringsubStr(Strings,inti,intj)在串s中，求從串的第i個字符開始連續(xù)j個字符所構(gòu)成的子串。intindex(Strings1,Strings2)如果串s2是s1的子串，則可求串s2在串s1中第一次出現(xiàn)的位置。順序結(jié)構(gòu)字符串ADT的定義structSeqString{ /*順序串的類型*/intMAXNUM; /*串允許的最大字符個數(shù)*/intn; /*串的長度，nMAXNUM*/char*c;};typedefstructSeqString*PSeqString;順序串示例s=“abcdefg”abcdefgs.n=7s.c0123456MAXNUM-1字符串ADT——創(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é)點*/ typedefstructStrNode*PStrNode;/*結(jié)點指針類型*/ structStrNode{ /*鏈串的結(jié)點結(jié)構(gòu)*/ charc; PStrNodelink; }; typedefstructStrNode*LinkString; /*鏈串的類型*/字符串結(jié)尾？長度？字符串的鏈接存儲示例sabcd^sabcd^不帶頭結(jié)點帶頭結(jié)點abcds帶尾指針的循環(huán)鏈表鏈接存儲字符串的基本運算創(chuàng)建空鏈串聯(lián)結(jié)兩個串取單鏈串的子串刪除子串追加方式插入子串子串定位[模式匹配]求串長創(chuàng)建帶頭結(jié)點的空鏈串LinkStringcreateNullStr_link(void){ LinkStringpst; pst=(LinkString)malloc(sizeof(structStrNode)); if(pst!=NULL) pst->link=NULL; else printf("Outofspace!\n");/*創(chuàng)建失敗*/ return(pst);}串模式匹配問題設(shè)有兩個串t和p:t=t0t1…tn-1，p=p0p1…pm-1

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

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

p0p1…pm-1

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

p0p1…pm-1

直到匹配成功或p移動到無法與t繼續(xù)比較為止（匹配失?。闼氐哪Ｊ狡ヅ洹ヅ渥哟甶ntindex(PSeqStringt,PSeqStringp)求p所指的串在t所指的串中第一次出現(xiàn)時，p所指串的第一個元素在t所指的串中的序號(下標+1)。

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

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