欧美三区_成人在线免费观看视频_欧美极品少妇xxxxⅹ免费视频_a级毛片免费播放_鲁一鲁中文字幕久久_亚洲一级特黄

【串和序列處理 4】Suffix Trie 子串匹配結構

系統 1625 0

Suffix Trie 又稱后綴Trie或后綴樹。它與Trie樹的最大不同在于,后綴Trie的字符串集合是由指定字符串的后綴子串構成的。比如、完整字符串"minimize"的后綴子串組成的集合S分別如下:

?

???????? s1=minimize

???????? s2=inimize

???????? s3=nimize

???????? s4=imize

???????? s5=mize

???????? s6=ize

???????? s7=ze

???????? s8=e

?

????? 然后把這些子串的公共前綴作為內部結點構成一棵"minimize"的后綴樹,如圖所示,其中上圖是Trie樹的字符表示,下圖是壓縮表示(詳細見《 Trie樹 》)。 可見Suffic Trie是一種很適合操作字符串子串的數據結構。 它和PAT tree在這一點上類似。

?

?

Suffix Trie的創建?

?

????? 標準Tire樹的每一個內部結點只有一個字符,也就是說公共前綴每一次只找一個。而Suffix Trie的公共前綴可以是多個字符,因此在創建Suffix Trie的時候,每插入一個后綴子串,就可能對內部結點造成一次分類。下面我們我們看一種后綴樹構造算法。以"minimize"為例:

?

????? 當插入子串時,發現葉子結點中的關鍵字與子串有公共前綴,則需要將該葉子結點分裂。如上圖第3到4步。否則,重新創建一個葉子結點來存放后綴,如上圖第1到2步

?

Suffix Trie的子串查詢

?

???? 如果在后綴樹T中查找子串P,我們需要這樣的過程:

???? (1) 從根結點root出發,遍歷所有的根的孩子結點:N1,N2,N3....

???? (2) 如果所有孩子結點中的關鍵字的第一個字符都和P的第一個字符不匹配,則沒有這個子串,查找結束。

???? (3) 假如N3結點的關鍵字K3第一個字符與P的相同,則匹配K3和P。

????????? 若 K3.length>=P.length? 并且K3.subString(0,P.length-1)=P,則匹配成功,否則匹配失敗。

????????? 若 K3.length<=P.length? 并且K3=P.subString(0, K3.length-1),則將子串P1=P.subString(K3.length, P.length); 即取出P中排除K3之后的子串。然后P1以N3為根結點繼續重復(1)~(3)的步驟。直到匹配完P1的所有字符,則匹配成功。否則匹配失敗。

?

????? 查詢效率:很顯然,在上面的算法中。匹配成功正好比較了P.length次字符。而定位結點的孩子指針,和Trie情況類似,假如字母表數量為d。則查詢效率為O(d*m),實際上,d是固定常數,如果使用Hash表直接定位,則d=1.

????? 因此,后綴樹查詢子串P的時間復雜度為O(m),其中m為P的長度。

?

Suffix Trie的應用

?

????? 標準Trie樹只適合前綴匹配和全字匹配,并不適合 后綴和子串匹配。而后綴樹在這方面則非常合適。

?

????? 另外 后綴樹也可以進行前綴匹配。 如果模式串P是字符串S的前綴的話,那么從根結點出發遍歷后綴樹,一定能夠尋找到一條路徑完全匹配完P。比如上圖: 模式串P=“mini”,主串S="minimize"。P從根節點出發,首先匹配到結點mi,然后再匹配孩子結點nimize。直到P中所有的字符都找到為止。所以P是S的前綴。

?

?

【串和序列處理 4】Suffix Trie 子串匹配結構


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 成年网站在线观看 | 性国产精品 | 天堂资源在线中文 | 久章草影院 | 国产精品va在线观看无 | 霍元甲之精武天下 | 天天影视插插 | 91免费看片| 欧美爽爽爽爽爽爽视频 | 色综合色狠狠天天久久婷婷基地 | 在线观看欧美三级 | 欧美在线视频一区 | 国产精品视频第一页 | 国产精品外围在线观看 | 欧美大片在线看免费观看 | 久久国产精品一区二区 | 成人欧美一区二区三区视频xxx | 色网综合 | 亚洲精品第一国产综合高清 | 日韩有码一区二区三区 | 国产精品亚洲第一区二区三区 | 97色在线 | 色爱综合网 | 国产精品婷婷 | 欧美a∨一区二区三区久久黄 | 91精品国产色综合久久 | 国产麻豆剧传媒精品好看的片 | 日本大片在线免费观看 | 热re91久久精品国产99热 | 在线精品国内外视频 | 国内精品视频在线观看 | 新神奇四侠免费完整版在线观看 | 国产1级片 | 99精品欧美一区 | 亚洲精品国产不卡在线观看 | 92午夜影院| 美女黄影院 | 91短视频免费 | 日本三级视频 | 欧美一级www| 91看片入口 |