回文制造机,至少要添加多少个字符

字符串正读和反读完全一样时,称为回文串.通过在字符串开头或结尾添加一定数量的字符使字符串变为回文串。
现给出长度n的仅包括大写字母的字符串s,请问至少添加多少字符,使之成为回文串。
例如
输入:
3
ABC
输出:
2

一下三个标签,到底需要什麽语言啊?
从第二个字符开始检查,以该字符为中心,将字符串分为两侧,检查字符少的一侧,是否在另一侧形成回文。一直检查到倒数第二个字符,记录其中回文最长的,最后看还多出几个字符,答案就是几。如果没有找到这样的字符,那么答案就是整个字符串长度

C


#include<bits/stdc++.h>
using namespace std;
char s[1010],t[1010];
int dp[1010][1010];
int main()
{
    scanf("%s",s);
    int l=strlen(s);
    for(int i=0,j=l-1;i<l;i++,j--)
        t[i]=s[j];
    for(int i=0;i<l;i++)
        for(int j=0;j<l;j++)
            if(s[i]==t[j])
                dp[i+1][j+1]=dp[i][j]+1;
            else
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
    printf("%d\n",l-dp[l][l]);
}

JAVA

import java.util.Scanner;
public class Main {

    /*1、基础:
    dp[i][j]:表示str[i...j]最少添加几个字符使得str[i...j]是回文串
    时间复杂度O(N^2),空间复杂度O(N^2)
    * */
    public static int[][] getDP(char[] str) {
        int[][] dp = new int[str.length][str.length];

        for (int j = 1; j < str.length; j++) {
            dp[j - 1][j] = str[j - 1] == str[j] ? 0 : 1;//两个字符情况  一个为0
            for (int i = j - 2; i > -1; i--) {
                if (str[i] == str[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp;
    }

    //根据dp和str得到新的字符串   时间复杂度O(N)
    public static String get1(String str) {
        if (str == null || str.length() < 2) {
            return str;
        }
        char[] chas = str.toCharArray();  //str转字符数组
        int[][] dp = getDP(chas);
        char[] res = new char[chas.length + dp[0][chas.length - 1]];  //返回的结果
        int i = 0;
        int j = chas.length - 1;
        int l = 0;
        int r = res.length - 1;
        while (i <= j) {
            if (chas[i] == chas[j]) {
                res[l++] = chas[i++];
                res[r--] = chas[j--];
            } else if (dp[i][j - 1] < dp[i + 1][j]) {//
                res[l++] = chas[j];
                res[r--] = chas[j--];
            } else {
                res[l++] = chas[i];
                res[r--] = chas[i++];
            }
        }

        return String.valueOf(res);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String res = get1(str);
        System.out.println(res);
    }
}

是只能在左或者右添加,还是左右同时都能加