Участник:Muradyan Armen/PALMKR

Материал из DISCOPAL
Перейти к: навигация, поиск

Python 3

https://www.spoj.com/problems/PALMKR/

 
def is_palindrome(s):
    reversed_s = ''
    for j in range(len(s)-1, -1, -1):
        reversed_s += s[j]
    if s == reversed_s:
        return True
    else:
        return False
 
def count_insertions(s):
 
    n = len(s)
 
    table = [[0 for i in range(n)]  
                for i in range(n)]
 
    l = 0
 
    for gap in range(1, n): 
        l = 0
        for h in range(gap, n): 
            if s[l] == s[h]: 
                table[l][h] = table[l + 1][h - 1] 
            else: 
                table[l][h] = (min(table[l][h - 1], table[l + 1][h]) + 1) 
            l += 1
 
    return(table)
 
def PALMKR(s):
 
    s_start = ''
    s_end = ''
 
    insertions = count_insertions(s)
 
    if is_palindrome(s):
        return s
 
    i = 0
    j = len(s) - 1
 
    while i <= j:
 
        if i == j:
            s_start += s[i]
            break
        else:
            if s[i] == s[j]:
                s_start = s_start + s[i]
                s_end = s[j] + s_end
                i += 1
                j -= 1
            else:
                if insertions[i + 1][j] == insertions[i][j - 1]:
                    if s[i] < s[j]:
                        s_start = s_start + s[i]
                        s_end = s[i] + s_end
                        i += 1
                    else:
                        s_start = s_start + s[j]
                        s_end = s[j] + s_end
                        j -= 1
                elif insertions[i + 1][j] < insertions[i][j - 1]:
                    s_start = s_start + s[i]
                    s_end = s[i] + s_end
                    i += 1
                else:
                    s_start = s_start + s[j]
                    s_end = s[j] + s_end
                    j -= 1
    return s_start + s_end
 
N = input()
N = int(N)
pals = []
lens = []
for i in range(N):
    word = input()
    pal = PALMKR(word)
    lens.append(len(pal) - len(word))
    pals.append(pal)
 
for i in range(len(pals)):
    print('Case', str(i+1) + ':', lens[i], pals[i])