#----------------------------------------------------------
# Written by Cathal Weakliam, 27 May 2012
# Program aligns three strings by common elements
# Written for the Amino Acid Badge
#-----------------------------------------------------------

#s1 = 'KVKILPKDRWTQHTTTGG'
#s2 = 'ILPKERWTGHTTTGGLNSF'
#s3 = 'ANKVKILPKDRFTQHATT'

s1 = raw_input('Type the first sequence: ')
s2 = raw_input('Type the second sequence: ')
s3 = raw_input('Type the third sequence: ')
print('')

lengthlist = [len(s1),len(s2),len(s3)]
length = [len(s1),len(s2),len(s3)]
length.sort()
length = length[-1]

def getScore(IA, IB, IX):
    score = 0
    for x in range(length):
        try:
            if s1[x+IX] == s2[x+IA] and s1[x+IX] == s3[x+IB]:
                score+=1
        except IndexError:
            score+=0
    return [score, IA, IB, IX]

def printResults(lst, s1, s2, s3):

    for i in range(length-lst[3]):
        s1 = '-'+s1
    for i in range(length-lst[1]):
        s2 = '-'+s2
    for i in range(length-lst[2]):
        s3 = '-'+s3

    while s1[0] == '-' and s2[0] == '-' and s3[0] == '-':
        s1 = s1.replace('-', '', 1)
        s2 = s2.replace('-', '', 1)
        s3 = s3.replace('-', '', 1)

    newlength = [len(s1),len(s2),len(s3)]
    newlength.sort()
    newlength = newlength[-1]

    while len(s1)<newlength:
        s1+='-'
    while len(s2)<newlength:
        s2+='-'
    while len(s3)<newlength:
        s3+='-'

    scoreline = '      '
    for i in range(newlength):
        if '-' in [s1[i],s2[i],s3[i]]:
            scoreline+=' '
        elif s1[i] == s2[i] and s1[i] == s3[i]:
            scoreline+='*'
        else:
            scoreline+=':'

    print('Seq1: '+s1+' :'+str(lengthlist[0]))
    print('Seq2: '+s2+' :'+str(lengthlist[1]))
    print('Seq3: '+s3+' :'+str(lengthlist[2]))
    print(scoreline)
    print(str(lst[0])+' columns of letters align')

lst = [0,0,0,0]
for IX in range(lengthlist[0]):
    for IA in range(lengthlist[1]):
        for IB in range(lengthlist[2]):
            newlst = getScore(IA, IB, IX)
            if newlst[0] > lst[0]:
                lst = newlst

printResults(lst, s1, s2, s3)

print('')
raw_input('Press ENTER to end the program.')