python實現動態(tài)規(guī)劃算法尋找最優(yōu)匹配子串問題

python3
difflib

import difflib

s1='agtcgtaatgc'
s2="cgaa"
mch=difflib.SequenceMatcher(a=s1,b=s2)
m=mch.find_longest_match(0,len(s1),0,len(s2))
print(s1[m.a:m.a+m.size],s2[m.b:m.b+m.size])
#cg cg

import numpy as np
s1='agtcgtaatgc'
s2="cgaa"
a = np.fromstring(s1,'S1')==np.fromstring(s2,'S1').reshape(-1,1)
i = max(range(len(s1)), key= a.trace)
print(s1[i:i+len(s2)])
#'cgta'

把較低的mismatch用字典保存一下，就好了。如：
def match(s1,s2):

length = len(s2)
result = ""
resultMissmatchCount=length
seqdict={}
for index,s in enumerate(s1[:-length]):
    missmatch = 0
    for j,k in zip(s1[index:index+length],s2): #[（s1[0],s2[0]),(s1[1],s2[1]),...]
        if j!=k:
            missmatch += 1
    if missmatch <= resultMissmatchCount: 
        seqdict[missmatch]=s1[index:index+length] 
        resultMissmatchCount = missmatch
minkey=min(seqdict.keys())
result = seqdict[minkey]
return result

算法什么的水平有限..?用最好理解的方式寫了一下。
這個記得時在刷題的時候看到的類似的，不過題目要求的時找出匹配的字段。
想象s2是一個窗口，在s1上從左向右滑動，每次滑動一個格子，計算現在字段的有多少錯配點位。最后找出最小的一個。
我這么寫這能找出最后一個。當然 <=改成<就是第一個了。

def match(s1,s2):
    length = len(s2)
    result = ""
    resultMissmatchCount=length
    for index,s in enumerate(s1[:-length]):
        missmatch = 0
        for j,k in zip(s1[index:index+length],s2):
            if j!=k:
                missmatch += 1
        if missmatch <= resultMissmatchCount:
            resultMissmatchCount = missmatch
            print s1[index:index+length]
            result = s1[index:index+length]
    return result