-
Notifications
You must be signed in to change notification settings - Fork 0
/
kmp.py
31 lines (27 loc) · 784 Bytes
/
kmp.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def kmp(s):
def longest_substring(k,bound):
for j in range(k-bound,k):
if k-j<=bound:
if s[j:k]==s[0:k-j]:
return k-j
return 0
result=[]
longest=-1
for k in range(1,len(s)+1):
longest=longest_substring(k,longest+1)
result.append(longest)
return result
if __name__=='__main__':
name=''
strings=[]
with open('rosalind_kmp.txt') as f:
for line in f:
if (len(name))==0:
name=line.strip()
else:
strings.append(line.strip())
string=''.join(s for s in strings)
print(' '.join(str(i) for i in kmp(string)))
a = ' '.join(str(i) for i in kmp(string))
fw = open("kmp-out.txt", "w")
fw.write(a)