kmp.py

# Preprocessing phase of Knuth-Morris-Pratt algorithm
import numpy as np
from fasta import readFASTA

d=readFASTA("rosalind_kmp.txt")
s=d.values()[0]

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 True:
        if s[j]==s[i]:
            answer[i]=j+1
            break
        else:
            if j==0:
                answer[i]=0
                break
            else:
                j=answer[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(x),