国产成人精品久久免费动漫-国产成人精品天堂-国产成人精品区在线观看-国产成人精品日本-a级毛片无码免费真人-a级毛片毛片免费观看久潮喷

您的位置:首頁技術文章
文章詳情頁

詳解KMP算法以及python如何實現

瀏覽:3日期:2022-07-10 17:12:52

算法思路

Knuth-Morris-Pratt(KMP)算法是解決字符串匹配問題的經典算法,下面通過一個例子來演示一下:

給定字符串'BBC ABCDAB ABCDABCDABDE',檢查里面是否包含另一個字符串'ABCDABD'。

1.從頭開始依次匹配字符,如果不匹配就跳到下一個字符

詳解KMP算法以及python如何實現

詳解KMP算法以及python如何實現

2.直到發現匹配字符,然后經過一個內循環嚴查字符串是否匹配

詳解KMP算法以及python如何實現

3.發現最后一個D不匹配,下面就該思考應該把字符串向右移動多少個位置呢?傳統做法可能是移動一格,KMP算法就創新在這里。KMP算法通過查詢一個Partial Match Table(表內存有字符串信息),然后計算出需要移動的步數,這個表后面會介紹怎么來的。

詳解KMP算法以及python如何實現

這里我們看到D前面是B,查表得到第二個B對應的是2,所以 移動數 = 已匹配字符數 - 查表所得數 也就是 6 - 2 = 4, 需要向右移動四格。

詳解KMP算法以及python如何實現

下面也是重復這個步驟

詳解KMP算法以及python如何實現

直到發現匹配或者字符長度超出(未發現匹配)。

Partial Match Table

那么這個查詢的表是怎么來的呢?仍然以'ABCDABD'為例

詳解KMP算法以及python如何實現

- 'A'的前綴和后綴都為空集,共有元素的長度為0;

- 'AB'的前綴為[A],后綴為[B],共有元素的長度為0;

- 'ABC'的前綴為[A, AB],后綴為[BC, C],共有元素的長度0;

- 'ABCD'的前綴為[A, AB, ABC],后綴為[BCD, CD, D],共有元素的長度為0;

- 'ABCDA'的前綴為[A, AB, ABC, ABCD],后綴為[BCDA, CDA, DA, A],共有元素為'A',長度為1;

- 'ABCDAB'的前綴為[A, AB, ABC, ABCD, ABCDA],后綴為[BCDAB, CDAB, DAB, AB, B],共有元素為'AB',長度為2;

- 'ABCDABD'的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB],后綴為[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的長度為0。

python實現

def partial_table(p): ’’’’’partial_table('ABCDABD') -> [0, 0, 0, 0, 1, 2, 0]’’’ prefix = set() res = [0] for i in range(1, len(p)): prefix.add(p[:i]) postfix = {p[j:i + 1] for j in range(1, i + 1)} #print(p[:i+1],prefix,postfix,prefix & postfix or {’’}) res.append(len((prefix & postfix or {’’}).pop())) return resdef kmp_match(s, p): m = len(s); n = len(p) cur = 0 # 起始指針cur table = partial_table(p) while cur <= m - n: #只去匹配前m-n個 for i in range(n): if s[i + cur] != p[i]:cur += max(i - table[i - 1], 1) # 有了部分匹配表,我們不只是單純的1位1位往右移,可以一次移動多位break else: return True # loop從 break 中退出時,else 部分不執行。 return Falseprint partial_table1('ABCDABD')print kmp_match('BBC ABCDAB ABCDABCDABDE', 'ABCDABD')

以上就是詳解KMP算法以及python如何實現的詳細內容,更多關于python實現KMP算法的資料請關注好吧啦網其它相關文章!

標簽: Python 編程
相關文章:
主站蜘蛛池模板: 欧美性xxxx极品高清 | 亚洲国产cao | 欧美成人全部免费观看1314色 | avtt天堂网 手机资源 | 男吃女下面刺激视频免费 | 欧美视频网站在线观看 | 97精品国产手机 | 美女张开腿让男人捅的视频 | 亚洲欧美7777 | 亚洲欧美第一 | 91精品最新国内在线播放 | 窝窝午夜精品一区二区 | 日韩精品一区二区三区免费观看 | 在线观看国产精品一区 | 国产麻豆福利a v在线播放 | 12至16末成年毛片视频 | 国产一级高清 | 国产女女视屏免费 | 91成人啪国产啪永久地址 | 天天看片天天爽_免费播放 天天看夜夜 | 最新欧美精品一区二区三区不卡 | 国产美女视频做爰 | 免费一级淫片aaa片毛片a级 | 欧美精品束缚一区二区三区 | 另类毛片 | 在线中文字幕亚洲 | 67id人成国产在线 | 91视频站| 美女免费毛片 | 国产一区二区三区四区在线 | 午夜爽爽 | 免费高清不卡毛片在线看 | 成年男女免费视频 | 亚洲精品国产一区二区在线 | 国产成人综合网在线观看 | 色在线网站免费观看 | 高清欧美性狂猛bbbbbbxxxx | 色偷偷女男人的天堂亚洲网 | 日本不卡一区二区三区在线观看 | 成人免费视频日本 | 成人日韩在线观看 |