d_neighbours.py~

def Neighbours(pattern,d):
    if d==0:
        return pattern
    if len(pattern)==1:
        return {'A','C','G','T'}
    Neighborhood=set()
    total_neighbours=set()
    SuffixNeighbors=Neighbours(pattern[1:],d)
    for x in SuffixNeighbors:
        if HammingDistance(pattern[1:],x)<d:
            for z in 'ACGT':
                Neighborhood.add(z+x)
        else:
            Neighborhood.add(pattern[0]+x)
    return Neighborhood

def HammingDistance(pattern1,pattern2):
    cn=0
    for u in range(len(pattern1)):
        if pattern1[u]!=pattern2[u]:
            cn+=1
    return cn

def reverse_compliment(dna):
    s=''
    dic={'A':'T','T':'A','C':'G','G':'C'}
    for i in reversed(range(len(dna))):
        s+=dic[dna[i]]
    return s

text=raw_input()
k,d=raw_input().split()
k,d=int(k),int(d)
possible_k_mers=[]
y=len(text)-k+1
maxi=0
for i in range(y):
    possible_k_mers.extend(list(Neighbours(text[i:i+k],d)))
count_k_mer_frequency=dict([(k_mer,0) for k_mer in possible_k_mers])
for k_mer in possible_k_mers:
    reverse_mer=reverse_compliment(k_mer)
    count_k_mer_frequency[reverse_mer]=0
for i in range(y):
    for k_mer in Neighbours(text[i:i+k],d):
        count_k_mer_frequency[k_mer]+=1
for k_mer in possible_k_mers:
    reverse_mer=reverse_compliment(k_mer)
    count_k_mer_frequency[k_mer]+=count_k_mer_frequency[reverse_mer]
    count_k_mer_frequency[reverse_mer]=count_k_mer_frequency[k_mer]

max_frequency=max(count_k_mer_frequency.values())
frequent_words=[]
for k_mer in count_k_mer_frequency:
        if count_k_mer_frequency[k_mer]==max_frequency:
            frequent_words.append(k_mer)
for key in frequent_words:
    print key,