字符串匹配问题

编辑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

字符串匹配问题

回答

相关问题