容忍最頻繁的子字符串

Question

我想找到一個字符串上最頻繁的子字符串（一定長度L），但允許一定的閾值或錯誤T（在子字符串的位置），顯然不會長於L本身。但是，迄今爲止我還沒有取得任何成就。我怎樣才能完成代碼？

stn='KLHLHLHKPLHLHLPHHKLH' 
L = 4 #(lenght of the pattern) 
T = 1 #(maximum tolerance or permitted error in any position of the query pattern) 

pattcount = {} 
for n in range(len(stn)- L+1): 
patt = stn[n:n+L] 
s_ = stn[i:i+len(patt)] 
if LevenshteinDistance(s_, patt) == T: 
pattcount[patt] = pattcount[patt] + 1 if pattcount.has_key(patt) else 1 

max = 0 
max_patt = [] 
for p,v in pattcount.iteritems(): 
if v > max: 
max_patt = [p] 
max = v 
elif v == max: 
max_patt += [p] 
print (" ".join(max_patt)) 

因此，例如，如果最頻繁的是KLH，如何能HLH，PLH，KLP，KPH的頻率膨脹KLH的頻率（以報告）？

Answer 1

>>> from Levenshtein import distance 
>>> from collections import defaultdict 
>>> tups = [stn[i:i+L] for i in range(0, len(stn) - (L - 1))] 
>>> print tups 
['KLHL', 'LHLH', 'HLHL', 'LHLH', 'HLHK', 'LHKP', 'HKPL', 'KPLH', 'PLHL', 'LHLH', 
'HLHL', 'LHLP', 'HLPH', 'LPHH', 'PHHK', 'HHKL', 'HKLH'] 
>>> d = defaultdict(list) 
>>> [d[x].append(y) for x in tups for y in tups 
            if x is not y and distance(x, y) <= T] 
>>> print d 
defaultdict(<type 'list'>, { 
       'KLHL': ['HLHL', 'PLHL', 'HLHL'], 
       'LHLP': ['LHLH', 'LHLH', 'LHKP', 'LHLH'], 
       'HLHK': ['HLHL', 'HLHL'], 
       'HLHL': ['KLHL', 'HLHK', 'PLHL', 'KLHL', 'HLHK', 'PLHL'], 
       'LHKP': ['LHLP'], 
       'LHLH': ['LHLP', 'LHLP', 'LHLP'], 
       'PLHL': ['KLHL', 'HLHL', 'HLHL']}) 
>>> s = sorted(d.iterkeys(), key=lambda k: len(d[k]), reverse=True) 
>>> print s 
['HLHL', 'LHLP', 'KLHL', 'LHLH', 'PLHL', 'HLHK', 'LHKP']