Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
56 lines (41 sloc) 1023 Bytes
#/usr/bin/python
import sys
# quadratic time (inefficient) common substring algorithm
def lcs(s1,s2):
max=0
ans={}
ret=[]
for i in range(len(s1)):
ans[i]={}
for j in range(len(s2)):
if s1[i]==s2[j]:
if i==0 or j==0:
ans[i][j]=1
else:
ans[i][j]=ans[i-1][j-1]+1
if ans[i][j]>max:
max=ans[i][j]
ret=[[i-max+1,j-max+1,max]]
elif ans[i][j]==max:
ret.append([i-max+1,j-max+1,max])
else:
ans[i][j]=0
return(ret)
try:
f=open(sys.argv[1],'rU')
except:
f=sys.stdin
value,key,s="","",{}
for x in f:
if x[0]!=">":
value=value+x.strip()
else:
if key!="": s[key]=value
value=''
key=x[1:].strip()
s[key]=value
first_key,first_value=s.popitem()
for x in s:
a=lcs(first_value,s[x])
first_value=a
print first_value
You can’t perform that action at this time.