题目描述

　回文词是一种对称的字符串,也就是说:一个回文词,从左向右读和从右向左读的结果都是一样的.任意给定一个字符串,通过插入若干个字符,都可以变成一个回文词.你的任务是写一个程序,求出给定字符串变成回文词所需插入的最小字符数.
比如,字符串”Ab3db”,在插入两个字符后可以变成一个回文词(“dAb3bAd”,”Adb3bdA”),然而,插入两个以下的字符无法使它变成一个回文词.

输入

　　输入文件的第一行包含一个数Ｎ，表示给定字符串的长度（３<=N<=5000）
　　　 文件的第二行是一个长度为Ｎ的字符串。字符串仅由大写字母，小写字母，和数字构成。大写字母和小写字母被认为是不同的。

输出

输出只包括一行，包含一个整数，表示需要插入的字符数。

思路

将这个字符串的正序和倒序跑一边最长公共子串，然后用长度减去它就可以了

var
  lena,lenb,i,j,k,max,n:longint;
  f:array[0..5000,0..5000] of integer;
  a,b,s,l:ansistring;
begin
  readln(n);
  readln(l);   
  k:=n;
      a:='';
      b:='';
      for i:=1 to k do
        a:=a+l[i];
      for i:=length(l) downto 1 do
        b:=b+l[i];
      lena:=length(a);
      lenb:=length(b);
      fillchar(f,sizeof(f),0);
      for i:=1 to lena do
        for j:=1 to lenb do
          if a[i]=b[j]
            then f[i,j]:=f[i-1,j-1]+1
            else if f[i-1,j]>f[i,j-1]
                then f[i,j]:=f[i-1,j]
                else f[i,j]:=f[i,j-1];
      if max