国产成人精品久久免费动漫-国产成人精品天堂-国产成人精品区在线观看-国产成人精品日本-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 編程
相關文章:
主站蜘蛛池模板: 天干天干天啪啪夜爽爽色 | 欧美精品毛片 | 国产精品久久久久免费a∨ 国产精品久久久久免费视频 | 99视频在线永久免费观看 | 久久91精品国产一区二区 | 国产成人精品曰本亚洲 | 一本色道久久综合亚洲精品 | 亚洲成人高清 | 欧美成年黄网站色高清视频 | 色综合久久久久久888 | 欧美成人性色xxxxx视频大 | 成人国产午夜在线视频 | 综合网站| 玖玖爱zh综合伊人久久 | 国产99视频精品免视看9 | 亚洲欧美日韩视频一区 | 免费精品久久久久久中文字幕 | 美女被免费网站在线软件 | 成 人 亚洲 综合天堂 | 亚洲免费网址 | 九九爱精品| 中文在线最新版天堂 | 亚洲www| 国产亚洲久久 | 国产乱子精品免费视观看片 | 狠狠88综合久久久久综合网 | 台湾黄三级高清在线观看播放 | 欧美全免费aaaaaa特黄在线 | 久久精品成人免费网站 | 美女视频一区二区三区 | 久草勉费视频 | 超矿碰人人超人人看 | 2020久久国产最新免费观看 | 国内自拍网站 | 91精品国产综合久久欧美 | 日鲁夜鲁鲁狠狠综合视频 | 玖草资源在线 | 在线观看亚洲免费 | 久久99国产精品 | 欧美一级特黄乱妇高清视频 | 国产欧美一区二区三区免费看 |