Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
37 lines (24 sloc) 612 Bytes
# Preprocessing phase of Knuth-Morris-Pratt algorithm
import numpy as np
from fasta import readFASTA
#d=readFASTA("rosalind_kmp.txt")
#s=d.values()[0]
s='CAGCATGGTATCACAGCAGAG'
answer=np.zeros(len(s),dtype=int)
answer[0]=-1
# s[0:ans[j]]=s[j+1-n:j+1]
for i in range(1,len(s)):
j=answer[i-1]
while s[j]!=s[i]:
if j==0:
break
else:
j=answer[j-1]
else:
answer[i]=j+1
f=open("kmp.out","w")
f.write("0 ")
print '0',
for x in range(1,len(s)):
f.write(str(answer[x])+' ')
print str(answer[x]),
You can’t perform that action at this time.