[工學(xué)]數(shù)據(jù)結(jié)構(gòu)——第4章串c-資料下載頁(yè)
2024-10-16 18:32本頁(yè)面
【正文】 /求出部分匹配信息 next數(shù)組 while (i amp。amp。 j) { if (j==1 || [i]==[j]) { i++。 j++。 } //i,j各增 1 else j=next[j]。 //i不變 ,j后退 } if (j=) return()。 //返回匹配模式串的首字符下標(biāo) else return(1)。 //返回不匹配標(biāo)志 } 設(shè)主串 s的長(zhǎng)度為 n，子串 t長(zhǎng)度為 m，在 KMP算法中求next數(shù)組的時(shí)間復(fù)雜度為 O(m)，在后面的匹配中因主串 s的下標(biāo) i不減即不回溯，比較次數(shù)可記為 n，所以 KMP算法總的時(shí)間復(fù)雜度為 O(n+m)。 【 例 】 設(shè)主串 s=ababcabcacbab，模式串 t=abcac。給出 KMP進(jìn)行模式匹配的過(guò)程。 解： 模式串對(duì)應(yīng)的 next數(shù)組如下表所示： j 0 1 2 3 4 t[j] a b c a c next[j] 1 0 0 0 1 a b a b c a b c a c b a b a b c a c i =2 j=2 （ a ）第 1 趟匹配 a b a b c a b c a c b a b a b c a c i =6 j=4 （ b ）第 2 趟匹配 a b a b c a b c a c b a b a b c a c i = 1 0 j =5 （ c ）第 3 趟匹配 , 返回 i t. le n g th =5 主串： 模式串： 失敗 修改為 i =2 j = n e x t[ j ] = 0 主串： 模式串： 失敗 修改為 i =6 j = n e x t[ j ] = 1 主串： 模式串： 采用 KMP算法的模式匹配過(guò)程 例如，設(shè)主串 s為 aaabaaaab，模式串 t為 aaaab。 t對(duì)應(yīng)的 next數(shù)組如表 。 j 0 1 2 3 4 t[j] a a a a b next[j] 1 0 1 2 3 a a a b a a a a b a a a a b i =3 j =3 （ a ） 第 1 趟匹配 主串： 模式串： 失敗 修改為 i =3 j = n e x t[ j ] = 2 a a a b a a a a b a a a a b i =3 j =2 （ b ） 第 2 趟匹配 主串： 模式串： 失敗 修改為 i =3 j = n e x t[ j ] = 1 a a a b a a a a b a a a a b i =3 j =1 （ c ） 第 3 趟匹配 主串： 模式串： 失敗 修改為 i =3 j = n e x t[ j ] = 0 a a a b a a a a b a a a a b i=3 j=0 （ d ） 第 4 趟匹配 主串： 模式串： 失敗 修改為 i =3 j = n e x t[ j ]= 1 a a a b a a a a b a a a a b i =9 j =5 （ f ） 第 5 趟匹配，返回 i t. le n g th =4 主串： 模式串： 修改為 i = i + 1 = 4 j = j + 1 = 0 采用KMP算法的模式匹配過(guò)程 缺陷： i=3,next[3]=2,而 2號(hào)位置與 3號(hào)位置的字符相同，沒(méi)有必須進(jìn)行下趟匹配。 這就是說(shuō)，若按上述定義得到 next[j]=k，而模式中 tj=tk，則主串中字符 si和模式串中字符 tj比較不等時(shí)，不需要再和 tk進(jìn)行比較，而直接和 tnext[k]進(jìn)行比較，換句話(huà)說(shuō)，此時(shí)的 next[j]應(yīng)和 next[k]相同。為此將 next[j]修正為 nextval[j]。 修正后的求 nextval數(shù)組的算法如下： public void GetNextval() //由模式串 t求出 nextval值 { int j=0,k=1。 nextval[0]=1。 while (j) { if (k==1 || [j]==[k]) { j++。k++。 if ([j]!=[k]) nextval[j]=k。 else nextval[j]=nextval[k]。 } else k=nextval[k]。 } } 修正后的 KMP算法如下： public int KMPIndex1() //修正的 KMP算法 { int nextval[MaxSize],i=0,j=0。 GetNextval(t,nextval)。 while (i amp。amp。 j) { if (j==1 || [i]==[j]) { i++。j++。 } else j=nextval[j]。 } if (j=) return()。 else return(1)。 } 與改進(jìn)前的 KMP算法一樣，本算法的時(shí)間復(fù)雜度也為O(n+m)。 【 例 】 設(shè)目標(biāo)串為 t=abcaabbabcabaacbacba，模式串 t=abcabaa。計(jì)算模式串 t的 nextval函數(shù)值。并畫(huà)出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過(guò)程。 解： 模式串 t的 nextval函數(shù)值如下表所示。 j 0 1 2 3 4 5 6 模式 t a b c a b a a next[j] 1 0 0 0 1 2 1 nextval[j] 1 0 0 1 0 2 1 利用 KMP算法的匹配過(guò)程如下： 第 1 次匹配 s = a b c a a b b a b c a b a a c b a c b a i =4 t = a b c a b a a j =4 失敗 修改為 i =4 j = n e x tv a l[ 4 ] = 0 第 2 次匹配 s = a b c a a b b a b c a b a a c b a c b a i =6 t = a b c a b a a j =2 失敗 修改為 i =6 j = n e x tv a l[ 2 ] = 0 第 3 次匹配 s = a b c a a b b a b c a b a a c b a c b a i =6 t = a b c a b a a j =0 失敗 修改為 i =6 j = n e x tv a l[ 0 ] = 1 修改為 i = i + 1 = 7 j = j + 1 = 0 第 4 次匹配 s = a b c a a b b a b c a b a a c b a c b a i = 1 4 t = a b c a b a a j =7 成功，返回 i t. le n g th =7
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1