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

Python 3

```
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])
```