<p><a href="http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm">Knuth-Morris-Pratt</a>算法是一个很好的方法,可以在另一个字符串中找到一个字符串(因为我看到了DNA,我猜你希望这个可以扩展到。。。十亿?)。</p>
<pre><code># Knuth-Morris-Pratt string matching
# David Eppstein, UC Irvine, 1 Mar 2002
from __future__ import generators
def KnuthMorrisPratt(text, pattern):
'''Yields all starting positions of copies of the pattern in the text.
Calling conventions are similar to string.find, but its arguments can be
lists or iterators, not just strings, it returns all matches, not just
the first one, and it does not need the whole text in memory at once.
Whenever it yields, it will have read the text exactly up to and including
the match that caused the yield.'''
# allow indexing into pattern and protect against change during yield
pattern = list(pattern)
# build table of shift amounts
shifts = [1] * (len(pattern) + 1)
shift = 1
for pos in range(len(pattern)):
while shift <= pos and pattern[pos] != pattern[pos-shift]:
shift += shifts[pos-shift]
shifts[pos+1] = shift
# do the actual search
startPos = 0
matchLen = 0
for c in text:
while matchLen == len(pattern) or \
matchLen >= 0 and pattern[matchLen] != c:
startPos += shifts[matchLen]
matchLen -= shifts[matchLen]
matchLen += 1
if matchLen == len(pattern):
yield startPos
</code></pre>
<p><a href="http://code.activestate.com/recipes/117214-knuth-morris-pratt-string-matching/">The link where I got the KMP python code</a>(和一个内置的,由于运行时常量的存在,对于小问题来说更快)。</p>
<p>为了提高性能,可以使用前缀表和字符串的哈希窗口作为基4整数(在生物学中,我们称它们为k-mers或oligos)。;)</p>
<p>祝你好运!</p>
<p><strong>编辑:</strong>还有一个很好的技巧,可以对包含第一个字符串中的每个前缀(n total)和第二个字符串中的每个前缀(n total)的列表进行排序。如果它们共享最大的公共子序列,则它们必须在排序列表中相邻,因此从排序列表中最接近的另一个字符串中查找元素,然后获取完全匹配的最长前缀。:)</p>