一个回文词，是从左到右读和从右到左读得到的结果是一样的字符串。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是编写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。
例如Ab3bd不是回文词，插入两个字符后构成的Adb3bdA即为回文词。
【输入文件】

从当前目录下的palin.in文件中取得输入。
输入文件的第一行包含一个整数N，表示给定字符串的长度，3≤N≤5000。
输入文件的第二行是一个长度为N的字符串。字符串仅由大写字母"A"到"Z"，小写字母"a"到"z"和数字"0"到"9"构成，区分大小写。
【输出文件】

输出文件是当前目录下的palin.out。
该文件只有一行，包含一个整数，表示需要插入的最少字符数。
【输入样例】

5
Ab3bd
【输出样例】

2
【样例说明】

Ab3bd中只需插入两个字符A，d就可编程回文Adb3bdA

f = open("palin.in", "r")
n= f.readline()
s1=f.readline()

关闭打开的文件

f.close()
n=int(n)
s2=s1[::-1]
m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩阵，为方便后续计算，比字符串长度多了一列
mmax=0 #最长匹配的长度
for i in range(len(s1)):
for j in range(len(s2)):
if s1[i]==s2[j]:
m[i+1][j+1]=m[i][j]+1
if m[i+1][j+1]>mmax:
mmax=m[i+1][j+1]
f=open("palin.out","w")
f.write(str(n-mmax))
f.close()

你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答


本次提问扣除的有问必答次数，将会以问答VIP体验卡（1次有问必答机会、商城购买实体图书享受95折优惠）的形式为您补发到账户。


因为有问必答VIP体验卡有效期仅有1天，您在需要使用的时候【私信】联系我，我会为您补发。