学步园

given a word,convert it into a pallindrome with minimum addition of letters to it.letters can be added anywhere in the word.for eg if yahoo is given result shud be yahoohay.give a optimize soln

方法1：

设字符串str1, 其倒置字符串str2, 求得str1和str2的最长公共序列str3

对str1,str2,str3做三路归并

方法2：

dp[i][dis]表示从i开始的长度为dis的字符串，要变为回文，最少添加多少字符

#include <iostream>
#include <stdio.h>

using namespace std;

const int N = 1000;
char ans[N];
int dp[N][N];
char s[N];

int tracebace(int p, int dis, int i, bool &flag) {
    if (dis == 0) {
        flag = false;
        return 0;
    }

    if (dis == 1) {
        flag = true;
        ans[i] = s[p];
        return 1;
    }

    if (s[p] == s[p+dis-1]) {
        ans[i] = s[p];
        return 1 + tracebace(p + 1, dis -2, i +1, flag);
    }
    if (dp[p][dis] == dp[p+1][dis-1] + 1) {
        ans[i] = s[p];
        return 1 + tracebace(p + 1, dis - 1, i + 1, flag);
    }

    else {
        ans[i] = s[p+dis-1];
        return 1 + tracebace(p, dis - 1, i + 1, flag);
    }
}

int main() {
    scanf("%s", s);
    memset(dp,0,sizeof(dp));
    int len = strlen(s);
    
    for (int dis = 2; dis <= len; ++dis ) {
        for (int i = 0; i <= len - dis; ++i) {
            if (s[i] == s[i + dis - 1])
                dp[i][dis] = dp[i + 1][dis - 2];
            else {
                dp[i][dis] = 1 + min(dp[i+1][dis-1], dp[i][dis-1]);
            }
        }
    }
    
    bool flag = true;
    int preLen = tracebace(0, len, 0, flag);
    int dis = flag ? 1 : 0;
    for (int i = preLen; i < len + dp[0][len]; ++i,++dis) {
        ans[i] = ans[preLen-dis-1];
    }

    ans[len + dp[0][len]] = 0;
    cout << ans<<endl;

    return 0;
}