# return the match score of two strings using simplified Sellers dynamic
# programming.

# return best match score between strings A and B
def matchscore(A,B):
    w,sp,sn= -1,2,-1    
    # assume simplified scoring scheme, no penalties for gaps and mismatches.
    A = "."+A  # add dummy chars so string index correspond to array lindex
    B = "."+B
    an,bn =len(A),len(B)
    # create 2D matrix anxbn rows index A, cols index B
    M = []
    for i in range(0,an): M.append( [0]*bn )
    for i in range(1,an):
        for k in range(1,bn):
            #M[i][k] = max(M[i-1][k],M[i][k-1],M[i-1][k-1]+score(i,k))
            #where score(i,k) = 1 if A[i]==B[i], 0 otherwise
            s = M[i-1][k-1]
            if A[i]==B[k]: s += sp
            else: s+= sn
            M[i][k] = max(s, M[i-1][k]+w, M[i][k-1]+w)
        # for k
    # for i
    return M[an-1][bn-1]
#mathscore

def maxscore(s):
    sp=2
    return len(s)*sp
#maxscore

# bestmatch, with conversion to lower case
def bestmatch(s,Au): # index of best match in A for s
    if len(Au)<1: raise Exception("empty array for bestmatch")
    s =s.lower()
    A=[""]*len(Au)
    for i in range(0,len(Au)): A[i] = Au[i].lower()
    bi = 0
    bx = matchscore(s,A[bi])
    for i in range(1,len(A)):
        mx = matchscore(s,A[i])
        if mx>bx:
            bx = mx
            bi = i
    #for i
    return (bi,bx)
#bestmatch

"""
Roster = ["Warlyn","Matt","Matthew","Michael","kamleen","Vivian","Jayson","Brandon","Brian","Jonila","John","KaiRui"]

(bi,bx) = bestmatch("Jason",Roster)
print(bi,bx,Roster[bi])
print(bestmatch("Jon",Roster))
"""