KMP串匹配并行算法的MPI實現(xiàn)

1、KMP串匹配的MPI實現(xiàn)一、簡單匹配算法KMP字符串模式匹配通俗點說就是一種在一個字符串中定位另一個串的高效算法。簡單 匹配算法的時間復(fù)雜度為O(m*n);KMP匹配算法?？梢宰C明它的時間復(fù)雜度為O(m+n).。先 來看一個簡單匹配算法的函數(shù)： int Index_BF ( char S , char T , int pos ) 返回第一個這樣的子串在串S中的下標(biāo)，否則返回-1*/=0；!= 0& Tj != 0)Tj)/*若串S中從第pos(S的下標(biāo)0WposStrLength(S)個字符起存在和串T相同的 子串，則稱匹配成功int i = pos, jwhile ( Si+jif ( Si

2、+j=j +; /繼續(xù)比較后一字符elsei +; j = 0; /重新開始新的一輪匹配if ( Tj = 0)return i; /匹配成功返回下標(biāo)elsereturn -1; /串S中(第pos個字符起)不存在和串T相同的子串 / Index_BF此算法的思想是直截了當(dāng)?shù)?將主串S中某個位置i起始的子串和模式串T相比較。即從j=0 起比較Si+j與Tj,若相等，則在主串S中存在以i為起始位置匹配成功的可能性， 繼續(xù)往后比較(j逐步增1)，直至與T串中最后一個字符相等為止，否則改從S串的下一 個字符起重新開始進(jìn)行下一輪的匹配，即將串T向后滑動一位，即i增1，而j退回至 0，重新開始新一輪的匹

3、配。例如：在串S=abcabcabdabba”中查找T= abcabd”(我們可以假設(shè)從下標(biāo)0開始)： 先是比較S0和T0是否相等，然后比較S1和T1是否相等我們發(fā)現(xiàn)一直比較到S5當(dāng)這樣一個失配發(fā)生時，T下標(biāo)必須回溯到開始，S下標(biāo)回溯的長度與T相同，然后S 下標(biāo)增1,然后再次比較。如圖：這次立刻發(fā)生了失配，T下標(biāo)又回溯到開始，S下標(biāo)增1,然后再次比較。如圖:所有字符都和S中相應(yīng)的字符匹配了。函數(shù)返回T在S中的起始下標(biāo)3。如圖:二、KMP算法KMP算法原理給定兩個串S= “S0S1Sn-1”和T= “T0T1Tm-1”，在主串S中尋找子串T的過程稱為模式匹配，T稱為模式串，若匹配成功，則返回模式

4、串T在主串S中第一次出現(xiàn)的 位置，若匹配失敗，則返回一 1。KMP算法可以在O(m+n)的時間數(shù)量級完成串的模式匹配操作，其改進(jìn)在于：每當(dāng)一趟匹 配過程中出現(xiàn)字符比較不等時，就利用已經(jīng)得到的“部分匹配”的結(jié)果將模式串“向右滑動” 盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。為了實現(xiàn)改進(jìn)算法，需要解決下述問題：當(dāng)匹配過 程中產(chǎn)生“失配”時，模式串“向右滑動”可行的距離有多遠(yuǎn)?換句話說，當(dāng)主串中第i個 字符與模式串中第j個字符“失配”時，主串中第i個字符應(yīng)與模式串中哪個字符再進(jìn)行比 較?假設(shè)當(dāng)“失配”時，模式串向右滑動的距離為k，則模式串中每個字符都對應(yīng)一個k值， 這個k值只依賴于模式串本身字符序列的構(gòu)成

5、，而與主串無關(guān)，用nextj表示與Tj相對 應(yīng)的k值(OWjWm-1)，則next定義如下：Nextj=-1 當(dāng) j=0;Nextj=maxk 當(dāng) k-1kj 且 T0Tk-1=Tj-kTj-1Nextj=0 其他假設(shè)模式串T= “abaabaac ”，根據(jù)公式計算next值。j01234567TabaabaacNext-10011234KMP算法的基本思想：在求得模式串的next值之后，匹配可按如下步驟進(jìn)行，假設(shè)i 和j分別指示主串和模式串中正待比較的字符，i和j的初值均為0。若在匹配過程中Si= Tj， 則i和j分別增1，繼續(xù)進(jìn)行比較；否則，i不變，而j退回到nextj的位置繼續(xù)比較， 如

6、此反復(fù)，直到出現(xiàn)下列兩種可能：當(dāng)j退回到某個n e x t值時字符比較相等，則i和j分別增1，繼續(xù)進(jìn)行匹配；當(dāng)j退回到一1，即模式串的第一個字符“失配”，則將主串向右滑動一個位置，使j=0， 即從主串下一個字符Si +1起和模式串重新開始匹配。例：若主串 S= a c a b a a b c a b a a b a a c b c” ，模式串 T = a b a a b a a c ” ，則匹配過程如下：第一趟：主串：a c a b a a b c a b a a b a a c b c ( i = 0, 1)模式串： a b ( j =0，1)此時 Next1 =0，因而 i 不變j =Ne

7、xtj = 0；第二趟：主串：a c a b a a b c a b a a b a a c b c ( i =1 )模式串： a ( j = 0 )此時 n e x t 0 = 一1，因而 i +， j = 0第三趟：主串：a c a b a a b c a b a a b a a c b c ( i =2 ,3,4 ,5,6 ,7 )模式串：a b a a b a ( j = 0,1,2,3,4,5 )此時 Next 5 = 2，因而i不變，j = Next j = 2第四趟：主串：a ca b a a b c a b a a b a ac b c ( i = 7 )模式串：( a b )

8、 a(j = 2 )此時 Next 2 = O,因而i不變，j = Nextj =0第五趟：主串：a ca b a a b c a b a a b a ac b c ( i = 7 )模式串： a ( j = 0 )此時 n e x t 0 = 1，因而 i +，j = 0第六趟：主串：acabaabcabaabaacbc ( i =8,9,10,11,12,13,14,15)模式串：a b a a b a a c ( j =0，1，2，3，4，5，6，7，8)此時j = 8，匹配成功。從例子可以看出，在第三趟，模式串中第5個字符與主串字符比較失配時，主串指針i 不變，繼續(xù)與模式串中第2個字符

9、比較，而T5=T2= a，匹配必然失敗，顯然此次比較是 多余的，這說明KMP算法中給出的next的求值方法不是最優(yōu)的，因此，對算法的優(yōu)化改進(jìn) 就是對next的求值方法的改進(jìn)。KMP算法實現(xiàn)1、假設(shè)以i和j分別指示正文t和模式p中正等待比較的字符，令i、j的初值為0； 若在匹配的過程中ti =pj,則i與j分別加1；否則i不變，而j退到nextj的位置 繼續(xù)比較(即j=nextj),r若相等，則指針各自增加1；否則j再退到下一個nextj值位 置，依次類推，直到下列兩種可能之一出現(xiàn)。j 退到某個 next 值(next.nextj.)時，ti = =pj成立，則 i，j 指 針各自加1后繼續(xù)比較

10、。j退到-1(即模式的第一個字符“失配)，此時需要將正文的指針i向右滑動一個 位置，即從正文的下一個字符ti+1起和模式p重新從頭開始比較。void getnext(string p ,int *next)int len = p.length();int k = 0;nextk=-1;/next0=-1int j = -1;while(klen) if(j= -1 | | pj = pk)k+; j+; nextk = j; else j = nextj; cout next 數(shù)組：；for(int x=0;xlen;x+)cout nextx ;2、求 next :next0= -1,j 假

11、設(shè) next0,nexti,.nexti的均已求出，現(xiàn)在要求 nexti+1 的值。由于在求解nexti時已經(jīng)得到pi之前最長真前綴和真后綴匹配的長度，設(shè)其值為 j，即：nexti = j ;如果此時進(jìn)一步有pj = = pi,則pi+1之前最長真前綴的和真 后綴匹配的長度就為j+1，且nexti+1=j+1;反之，若pj!=pi,注意到，求pi+1之前 的最長真前綴和真后綴匹配問題本質(zhì)上仍然是一個模式匹配問題，只是在這里模式和正文都 是同一個串p而已。因此pj!=pi時，應(yīng)檢查pnextj與pi是否相等，若相等，則 nexti+1 =nextj+1,若仍然不想等，再取pnextnextj與p

12、i進(jìn)行比較，直到要將 p-1 與pi進(jìn)行比較為止，此時nexti+1 =0。void getnext(string p ,int *next)int len = p.length();int k = 0;nextk=-1;/next0=-1int j = -1;while(klen) if(j= -1 | | pj = pk)k+; j+; nextk = j; else j = nextj; cout next 數(shù)組：；for(int n=0;np.length();n+)cout nextn S0 != S1,S1 != S2,所以 S1!=T0,S2!=T0.還是從 理論上間接比較了。K

13、MP算法時間復(fù)雜度的計算：while循環(huán)使得執(zhí)行次數(shù)出現(xiàn)了不確定因素。我們將用到時間 復(fù)雜度的攤還分析中的主要策略，簡單地說就是通過觀察某一個變量或函數(shù)值的變化來對零 散的、雜亂的、不規(guī)則的執(zhí)行次數(shù)進(jìn)行累計。KMP的時間復(fù)雜度分析可謂攤還分析的典型。 我們從上述程序的j值入手。每一次執(zhí)行while循環(huán)都會使j減小(但不能減成負(fù)的)，而 另外的改變j值的地方只有第五行。每次執(zhí)行了這一行，j都只能加1；因此，整個過程中 j最多加了 n個1。于是，j最多只有n次減小的機會(j值減小的次數(shù)當(dāng)然不能超過n，因 為j永遠(yuǎn)是非負(fù)整數(shù))。這告訴我們，while循環(huán)總共最多執(zhí)行了 n次。按照攤還分析的說 法，平

14、攤到每次for循環(huán)中后，一次for循環(huán)的復(fù)雜度為O(1)。整個過程顯然是O(n)的。 這樣的分析對于后面P數(shù)組預(yù)處理的過程同樣有效，同樣可以得到預(yù)處理過程的復(fù)雜度為O(m)。其實，KMP的預(yù)處理本身就是一個T串“自我匹配”的過程三、改進(jìn)的KMP算法3.1算法的基本思想雖然模式匹配KMP算法的引入避免了算法中頻繁的回溯，普遍提高了模式匹配的工作效 率,但是經(jīng)過分析，對KMP算法掃描部分還可做進(jìn)一步的改進(jìn)，下面介紹改進(jìn)KMP算法的基本 思想?；舅枷?每當(dāng)某趟匹配失敗時,i指針不必回溯，而是利用己經(jīng)得到的部分匹配結(jié)果, 看看是否有必要將i的值進(jìn)行調(diào)整，然后再將模式向右滑動 若干位置后繼續(xù)比較。改進(jìn)

15、的 KMP算法中的i不是保持不變，而是增加了，這就意味著加快了模式匹配的進(jìn)度。針對KMP算法的不足，下面給出新的next計算公式：Nextj= 1 當(dāng) j=0;Nextj= 1 當(dāng) k-1kj 且 T0Tk-1 =Tj-kTj-1 且 Tk=TjNextj= maxk 當(dāng) k-1kj 且 T0Tk-1 =Tj-kTj-1 且 Tk!=TjNextj=0 其他公式(2)是主要對公式(1)的第二種情況給出了改進(jìn)，從而減少了多余的比較次數(shù)。對模式串 T= a b a a b a a c ”，根據(jù)公式(2 )計算n e x t值。j01234567模式串a(chǎn)baabaacNext-10-11-1-1-1

16、4根據(jù)改進(jìn)的next值，上例的匹配過程如下：第一趟： 主串：a e a b a a b c a b a a b a a e b c ( i = 0,1 )模式串：a b ( j = 0,1 )此時 next1 =0，因而 i 不變，j = next j = 0；第二趟：主串：a c a b a a b c a b a a b a a e b c ( i = 1 )模式串：a ( j=0 )此時 n e x t 0 =一 l，因而 i +，j =0第三趟： 主串：a c a b a a b c a b a a b a a e b c ( i=2,3,4,5,6,7)馘串：a b a a b a

17、( j = 0,1,2,3,4,5)此時 n e x t 5 =一 1，因而 i + j = 0第四趟：主串：a c a b a a b c a b a a b a a e b e (i=8,9,10,11,12,13,14,15) 模式串：a b a a b a a c ( j =0,1,2,3,4,5,6,7,8) 此時 j = 8，匹配成功。3.2 KMP改進(jìn)算法的實現(xiàn)void getnext(char *t,int *next) int i,j;int tlen=strlen(t);i=0;j=-1;next0=-1;while(itlen)if(j=-1 | ti=tj)i+;j+;

18、if(ti=tj)nexti=-1;elsenexti=j;elsej=nextj;int kmp_match(char *s,char *t,int pos)int i,j,slen,tlen;int *next=(int *)malloc(sizeof(int);slen=strlen(s);tlen=strlen(t);*next=tlen;getnext(t,next);i=pos;j=。；while(islen & jtlen)if(j=-1 | si=tj)i+;j+;else j=nextj;if(j0)?(myid*n-m):0,tlen,myid);elsekmp_match(T,P,next,(myid*n-m0)?(myid*n-m):0,(myid+1)*n,myid);MPI_Finalize();free(next);return 0;4.3運行結(jié)果顯示在 192.168.150.217 上:編譯:rootIO leinpi# gcc gen_pe