国产免费AV|泡泡玛特欧洲总部将设在伦敦|中文天堂网www新版资源在线|一本久道综合在线中文|国精产品一二三产区的使用方法|香蕉鱼在线观看|www.27eee

ELEOK

標(biāo)題: 數(shù)據(jù)結(jié)構(gòu)KMP算法C語(yǔ)言源程序 [打印本頁(yè)]

作者: coolice 時(shí)間: 2020-4-25 17:08
標(biāo)題: 數(shù)據(jù)結(jié)構(gòu)KMP算法C語(yǔ)言源程序

1.概述.

快速模式匹配算法，簡(jiǎn)稱 KMP 算法，是在 BF 算法基礎(chǔ)上改進(jìn)得到的算法。 BF 算的實(shí)現(xiàn)過(guò)程就是 "傻瓜式" 地用模式串（假定為子串的串）與主串中的字符一一匹配，算法執(zhí)行效率不高，所以為了減少算法的時(shí)間復(fù)雜度，特引出KMP算法

2.基本原理
example:

由此可以看出，每次匹配失敗后模式串移動(dòng)的距離不一定是 1，某些情況下一次可移動(dòng)多個(gè)位置，這就是 KMP 模式匹配算法

模式串移動(dòng)距離的判斷：
每次模式匹配失敗后，計(jì)算模式串向后移動(dòng)的距離是 KMP 算法中的核心部分。
其實(shí)，

匹配失敗后模式串移動(dòng)的距離和主串沒(méi)有關(guān)系，只與模式串本身有關(guān)系。

給每個(gè)模式串配備一個(gè)數(shù)組（例如 next[]），用于存儲(chǔ)模式串中每個(gè)字符對(duì)應(yīng)指針 j 重定向的位置（也就是存儲(chǔ)模式串的數(shù)組下標(biāo)），比如 j=4，則該字符匹配失敗后指針 j 指向模式串中第4 個(gè)字符
3.實(shí)現(xiàn) next 數(shù)組的 C 語(yǔ)言代碼：

4.next 數(shù)組的缺陷及改進(jìn)

當(dāng)匹配失敗時(shí)，Next 函數(shù) 開(kāi)始繼續(xù)進(jìn)行模式匹配，但是從圖中可以看到，這樣做是沒(méi)有必要的，純屬浪費(fèi)時(shí)間

出現(xiàn)這種多余的操作，問(wèn)題在當(dāng) T[i-1]==T[j-1] 成立時(shí)，沒(méi)有繼續(xù)對(duì) i++ 和 j++ 后的 T[i-1] 和 T[j-1] 的值做判斷。改進(jìn)后的 Next 函數(shù)如下所示：

5.KMP的實(shí)現(xiàn)：附件

KMP算法C源碼.rar (1.18 KB, 售價(jià): 1 E幣)

歡迎光臨 ELEOK (http://www.afoofa.cn/)