lrep.py

from collections import defaultdict
import operator

tree=defaultdict(list)
rtree=defaultdict(list)
loc=dict()
sublen=dict()
subcnt=defaultdict(int)
tlen=defaultdict(int)

with open("rosalind_lrep.txt","rU") as f:
    base=f.readline().strip()
    n=int(f.readline().strip())
    for line in f:
        s=line.split()
        tree[s[0]].append(s[1])
        rtree[s[1]]=s[0]
        loc[s[1]]=int(s[2])
        sublen[s[1]]=int(s[3])

def count_substrings(s):
    if len(tree[s])==0:
        subcnt[s]=1
    else:
        for t in tree[s]:
            count_substrings(t)
            subcnt[s]+=subcnt[t]

def substring_len(s):
    for x in tree[s]:
        tlen[x]=sublen[x]+tlen[s]
        substring_len(x)
        
count_substrings('node1')
substring_len('node1')

L=sorted([(x,subcnt[x],tlen[x]) for x in tree.keys() if subcnt[x]>=n],key=operator.itemgetter(2),reverse=True)
y=L[0][0]
s=''
while y in rtree:
    s=base[loc[y]-1:loc[y]+sublen[y]-1]+s
    y=rtree[y]
print s