字符串匹配問題

編輯2：我設法找到帶有後綴樹Tree::Suffix perl包的解決方案。感謝MarcoS爲trie的想法。我從中發現，後綴樹也可以使用。 Tree::Trie perl包被實現爲哈希散列，我想這就是它緩慢的原因。我試了一下，然後回到Tree::Suffix。感謝所有其他人提供不同算法的鏈接。我已經試圖爲這裏提到的每種算法編寫代碼，我自己作爲一個學習過程字符串匹配問題

編輯1：我將標題從perl string-match problem更改爲string-match problem。

假設我有兩個字符串，也就是說，
S1 = ACGAGGATAGTATGCCACACAATGAGTACCCGTAC
S2 = CAGTATTGCACGTTGTAAAGTTACCCAGGTACGATGACAGTGCGTGAGCATACGAGGATAGTATGCCA

我最初想以檢查串S1的發生（沒有或1個錯）的S2。我已經爲此寫了perl代碼。現在

，我想它發展到

1）搜索S1在S2 K-不匹配。
2）搜索S2中S1的prefix（是，前綴，而不是後綴）的發生。如果查看示例，字符串：ACGAGGATAGTATGCCA發生在S1的開始處S2的末尾。
3）如果可能，搜索k-不匹配的前綴。

問題是我有大約1億個這樣的S2字符串。但S1保持不變，並且對於給定的問題具有定義的恆定長度。在文獻中是否有一個有效的算法可用於解決這個問題？

S1在50到80個字符之間變化。另外，我最初對解決problem 2感興趣。

非常感謝。

來源

2011-09-26 Arun

我不敢相信，除非你能找到一個本地模塊來實現k-mismatch算法，否則在perl中編寫它是很有效的。 – Alnitak

難道[Trie]（http://en.wikipedia.org/wiki/Trie）對你的目的有幫助嗎？ – MarcoS

也許看到：http://stackoverflow.com/questions/1672782/fastest-way-to-find-mismatch-positions-between-two-strings-of-the-same-length –

您可以根據自己的需要修改Aho-Corasick algorithm。

來源

2011-09-26 13:42:12 mkb

如需近似匹配，請查看在agrep中使用的http://en.wikipedia.org/wiki/Bitap_algorithm。

來源

2011-09-26 18:00:52 mcdowella

字符串匹配問題

回答

相關問題