串的模式匹配算法實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上串的模式匹配算法實(shí)驗(yàn)報(bào)告篇一：串的模式匹配算法串的匹配算法bruteForce(bF)算法匹配模式的定義設(shè)有主串s和子串T，子串T的定位就是要在主串s中找到一個(gè)與子串T相等的子串。通常把主串s稱為目標(biāo)串，把子串T稱為模式串，因此定位也稱作模式匹配。模式匹配成功是指在目標(biāo)串s中找到一個(gè)模式串T；不成功則指目標(biāo)串s中不存在模式串T。bF算法brute-Force算法簡稱為bF算法，其基本思路是：從目標(biāo)串s的第一個(gè)字符開始和模式串T中的第一個(gè)字符比較，若相等，則繼續(xù)逐個(gè)比較后續(xù)的字符；否則從目標(biāo)串s的第二個(gè)字符開始重新與模式串T的第一個(gè)字符進(jìn)行比較。以此類推，若從模式串T的

2、第i個(gè)字符開始，每個(gè)字符依次和目標(biāo)串s中的對應(yīng)字符相等，則匹配成功，該算法返回i；否則，匹配失敗，算法返回0。實(shí)現(xiàn)代碼如下：/*返回子串T在主串s中第pos個(gè)字符之后的位置。若不存在，則函數(shù)返回值為0./*T非空。intindex(strings,stringT,intpos)inti=pos;/用于主串s中當(dāng)前位置下標(biāo)，若pos不為1則從pos位置開始匹配intj=1;/j用于子串T中當(dāng)前位置下標(biāo)值while(ij=1；if(j>T0)returni-T0;elsereturn0;bF算法的時(shí)間復(fù)雜度若n為主串長度，m為子串長度則最好的情況是：一配就中，只比較了m次。最壞的情況是：主串

3、前面n-m個(gè)位置都部分匹配到子串的最后一位，即這n-m位比較了m次，最后m位也各比較了一次，還要加上m,所以總次數(shù)為：(n-m)*m+m=(n-m+1)*m從最好到最壞情況統(tǒng)計(jì)總的比較次數(shù)，然后取平均，得到一般情況是o(n+m).篇二：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-串實(shí)驗(yàn)四串【實(shí)驗(yàn)?zāi)康摹?、掌握串的存儲表示及基本操作；2、掌握串的兩種模式匹配算法：bF和Kmp。3、了解串的應(yīng)用?！緦?shí)驗(yàn)學(xué)時(shí)】2學(xué)時(shí)【實(shí)驗(yàn)預(yù)習(xí)】回答以下問題：1、串和子串的定義串的定義：串是由零個(gè)或多個(gè)任意字符組成的有限序列。子串的定義：串中任意連續(xù)字符組成的子序列稱為該串的子串。2、串的模式匹配串的模式匹配即子串定位是一種重要的串運(yùn)算。設(shè)s

4、和t是給定的兩個(gè)串，從主串s的第start個(gè)字符開始查找等于子串t的過程稱為模式匹配，如果在s中找到等于t的子串，則稱匹配成功，函數(shù)返回t在s中首次出現(xiàn)的存儲位置（或序號）；否則，匹配失敗，返回0?！緦?shí)驗(yàn)內(nèi)容和要(:串的模式匹配算法實(shí)驗(yàn)報(bào)告)求】1、按照要求完成程序exp4_1.c，實(shí)現(xiàn)串的相關(guān)操作。調(diào)試并運(yùn)行如下測試數(shù)據(jù)給出運(yùn)行結(jié)果：?求“Thisisaboy”的串長；?比較”abc?3”和“abcde“；?表示空格?比較”english”和“student“；?比較”abc”和“abc“；?截取串”white”，起始2，長度2；?截取串”white”，起始1，長度7；?截取串”white”

5、，起始6，長度2；?連接串”asddffgh”和”12344”；#include#include#definemAxsIZe100#defineeRRoR0#defineoK1/*串的定長順序存儲表示*/typedefstructchardatamAxsIZe;intlength;sqstring;intstrInit(sqstring*s);/*初始化串*/intstrcreate(sqstring*s);/*生成一個(gè)串*/intstrLength(sqstring*s);/*求串的長度*/intstrcompare(sqstring*s1,sqstring*s2);/*兩個(gè)串的比較*/in

6、tsubstring(sqstring*sub,sqstring*s,intpos,intlen);/*求子串*/intstrconcat(sqstring*t,sqstring*s1,sqstring*s2);/*兩個(gè)串的連接*/*初始化串*/intstrInit(sqstring*s)s->length=0;s->data0=0;returnoK;/*strInit*/*生成一個(gè)串*/intstrcreate(sqstring*s)printf("inputstring:");gets(s->data);s->length=strlen(s-&g

7、t;data);returnoK;/*strcreate*/*（1）-求串的長度*/intstrLength(sqstring*s)returns->length;/*strLength*/*（2）-兩個(gè)串的比較，s1>s2返回>0，s1intstrcompare(sqstring*s1,sqstring*s2)inti;for(i=0;ilengthi+)if(s1->datai>s2->datai)return1;if(s1->dataidatai)return-1;return0;/*strcompare*/*（3）-求子串，sub為返回的子串，

8、pos為子串的起始位置，len為子串的長度*/intsubstring(sqstring*sub,sqstring*s,intpos,intlen)inti;if(poss->length|lens->length-pos+1)returneRRoR;sub->length=0;for(i=0;isub->datai=s->datai+pos-1;sub->length+;sub->datai=0;returnoK;/*substring*/*（4）-兩個(gè)串連接，s2連接在s1后，連接后的結(jié)果串放在t中*/intstrconcat(sqstring*t

9、,sqstring*s1,sqstring*s2)inti=0,j=0;while(ilength)t->datai=s1->datai;i+;while(jlength)t->datai+=s2->dataj+;t->datai=0;t->length=s1->length+s2->length;returnoK;/*strconcat*/intmain()intn,k,pos,len;sqstrings,t,x;doprintf("n-string-n");printf("1.strLentghn");

10、printf("2.strcomparen");printf("3.substringn");printf("4.strconcatn");printf("0.exITn");printf("n-string-n");printf("ninputchoice:");scanf("%d",getchar();switch(n)case1:printf("n*showstrLength*n");strcreate(printf("

11、strLengthis%dn",strLength(break;case2:printf("n*showstrcompare*n");strcreate(strcreate(k=strcompare(/*（5）-調(diào)用串比較函數(shù)比較s，t*/if(k=0)printf("twostringequal!n");elseif(kprintf("firststringelseprintf("firststring>secondstring!n");break;case3:printf("n*showsubs

12、tring*n");strcreate(printf("inputsubstringpos,len:");scanf("%d,%d",if(substring(elseprintf("posorleneRRoR!n");break;case4:printf("n*showsubconcat*n");strcreate(strcreate(if(strconcat(elseprintf("concateRRoR!n");break;case0:exit(0);default:break;

13、while(n);return0;2、按照要求完成程序exp4_2.c，實(shí)現(xiàn)bFintlength;sqstring;intstrcreate(sqstring*s);intindexbf(sqstring*s,sqstring*t,intpos);/*串的模式匹配bF*/voidgetnext(sqstring*t,intnext);/*Kmp求next值*/篇三：字符串模式匹配算法綜述字符串模式匹配算法綜述摘要：字符串匹配問題是在給定符號序列（稱為文本）中按照一定的匹配條件，搜索給定符號序列或給定符號序列集合中元素（稱為模式）出現(xiàn)位置的搜索問題。該問題是計(jì)算機(jī)科學(xué)的基礎(chǔ)問題之一，被廣泛的應(yīng)

14、用于各種涉及文字和符號處理的領(lǐng)域中，是網(wǎng)絡(luò)安全、信息檢索、計(jì)算生物學(xué)等重要領(lǐng)域的關(guān)鍵問題。本文主要介紹了bF算法、Kmp算法、bm算法、bmh算法、Ac算法和Ac-bm算法。關(guān)鍵詞：模式匹配，bF算法，Kmp算法，改進(jìn)算法，bm算法，Ac算法，Ach算法。0.前言字符串是一種線性表,它在計(jì)算機(jī)應(yīng)用系統(tǒng)中如文本編輯、情報(bào)檢索、自然語言翻譯有著廣泛的應(yīng)用。在這些應(yīng)用中常常需要在一堆文字符串中檢測是否有某一指定的字符串。設(shè)pattern(下文簡稱p)和Text(下文簡稱T)是給定的兩個(gè)字符串,在字符串T中尋找等于p的子串的過程稱為模式匹配,其中字符串T稱為主串,字符串p稱為模式串。如果在字符串T中找

15、到等于p的子串,則稱匹配成功,否則匹配失敗。比較著名的模式匹配算法有bF算法、Kmp算法、Ac算法和bm算法,本文對所述算法進(jìn)行探討。隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，計(jì)算機(jī)網(wǎng)絡(luò)在國民經(jīng)濟(jì)中發(fā)揮了日益重要的作用，己成為人們?nèi)粘Ｉ钪胁豢扇鄙俚囊徊糠?。同時(shí)，網(wǎng)絡(luò)安全也日益引起人們的關(guān)注。1.模式匹配算法1.1單模式匹配算法1.1.1bF（bruceForce）算法1.算法思想從文本字符串T的第一個(gè)字符起和模式字符串p中的第一個(gè)字符開始比較，若相等，逐個(gè)比較后續(xù)字符，否則從文本字符串的下一個(gè)字符起再重新和模式字符串的第一個(gè)字符比較。2.算法描述對于文本字符串T0?Tk?Ti?Tm?k?1?Tn模式字符串p

16、0?pj?pm（1）p和T從左端對齊，使得p0與T0對齊；（2）從左到右匹配p與T的字符，直到出現(xiàn)不匹配的情況，則執(zhí)行（3），或是p己被完全匹配的情況則結(jié)束比較；（3）將p右移一個(gè)字符，重新從p的第一個(gè)字符開始匹配；（4）重復(fù)上述（2）過程，直到p被完全匹配，或p移到T的右端。1.1.2Kmp（Knuthmorrispratt）算法Kmp算法是Knuth等人在bF算法的基礎(chǔ)上提出來的。從本質(zhì)上講，Kmp算法就是出現(xiàn)不匹配情況下帶有智能指針初始化的bF算法。為了在不匹配時(shí)重新定位指針，Kmp算法需要進(jìn)行預(yù)處理算出一個(gè)next數(shù)組來。1.基本思想Kmp算法利用己匹配成功部分的信息，即前綴（模式字符

17、串中存在的相同子串），可以使模式字符串向前推進(jìn)若干個(gè)字符位置，而不只是一個(gè)字符，避免了重復(fù)比較，同時(shí)也實(shí)現(xiàn)了文本字符串指針的無回溯。2.算法描述當(dāng)模式匹配執(zhí)行到比較字符Ti和pj，其中l(wèi)=i=n，l=j=m。（l）若Ti=pj則繼續(xù)往右做匹配檢測，即對Ti?1和pj?1進(jìn)行匹配檢測。（2）若Ti?pj當(dāng)j=l，則對Ti?1和pj進(jìn)行匹配檢測，即把模式和正文向右移動一位再從模式的第一個(gè)字符進(jìn)行匹配；若l0j?1?next?j?max?k|0?k?j且p0?pk?1?pj?k?1?pj?1?集合非空?1其他情況?1.1.3改進(jìn)的字符串匹配算法字符串模式匹配算法要解決的關(guān)鍵問題是：在模式與文本在某個(gè)

18、位置比較失敗時(shí)，如何使模式串窗口向右移動最佳距離，盡量多的跳過不必要比較的字符，減少匹配的次數(shù)，并使產(chǎn)生這種距離的算法復(fù)雜度降低和易于理解。通過對現(xiàn)有的各種字符串匹配算法進(jìn)行分析研究，我們提出一種改進(jìn)算法，該算法簡單實(shí)用，便于理解。1.基本思想與Kmp算法類似，在模式串的匹配過程中，字符比較采用符合人們習(xí)慣的從左到右順序，模式窗口也是從左到右移動。2.算法描述設(shè)當(dāng)前的比較窗口是?TiTi?1?Ti?m?1?，在某次比較過程中失敗于pj處，即前j個(gè)字符匹配成功：TiTi?1?Ti?j?1=p0p，而Ti?jpj。首先定義一個(gè)函1?pj?1數(shù)s來確定正文中出現(xiàn)的字符x在模式p中的位置，考慮到要使用

19、模式對應(yīng)窗口后的第一個(gè)字符，在模式串p中補(bǔ)充一個(gè)字符pm與之對應(yīng)，以使和文本中的窗口對齊，這樣p?p0p，如圖1所示。1?pm?圖1模式串p與主串T對應(yīng)位置函數(shù)s的定義如下：x?p0?pk?1?(j?k?m,j?m)?k?1?k?qx?p0?pk?1?(j?k?m,j?m)?s(x)?其中q?maxq|pq?x,0?q?k?1?p0?Ti時(shí)?1其中：x取當(dāng)前窗口匹配失敗位置j及其后的字符即x=Ti?k，jkm，并且x取值位置的變化引起前面子串p0p長度的變化。s(x)函數(shù)實(shí)質(zhì)是用來1?pk?1求匹配失敗時(shí)模式串的向右移動距離。有以下三種情況：（1）當(dāng)x不在前面的子串(子串包括p本身)中時(shí)，啟發(fā)

20、移動的距離是子串的字符個(gè)數(shù)；（2）在子串中從后向前查找第一個(gè)與x相同的字符，啟發(fā)移動的距離是它們之間的間隔距離；（3）如果p0?Ti，子串p0p的下標(biāo)0-1-1，為統(tǒng)一使用函數(shù)s(x)而1?pk?1規(guī)定的取值。圖2改進(jìn)算法的具體實(shí)現(xiàn)流程我們采用3個(gè)位置的字符：Ti?j、Ti?j?1、Ti?m進(jìn)行計(jì)算，之所以考慮用Ti?j?1、Ti?m來參與決定模式窗口的移動距離，是因?yàn)槿缜懊娴淖址l(fā)生不匹配，則模式至少向后移動一個(gè)位置，二者處于移動后的窗口之內(nèi)，作為新窗口之內(nèi)的字符，Ti?j?1、它們也要求模式滑過一定距離，Ti?m也需要與模式中與之相同的字符對齊，所以考查由它們來啟發(fā)的距離是自然的，尤其是當(dāng)二者不在它們前面的子串中