ac

给定一个字符串str，再给定str的最长回文子序列字符串strlps, 请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。进阶问题比原问题多了一个参数，请做到时间复杂度比原问题的实现低。

A1B21C
121

AC1B2B1CA

str="A1B21C"，strlps="121"，返回"AC1B2B1CA"或者"CA1B2B1AC"，总之，只要是添加的字符数最少，只返回其中一种结果即可。

leftPart + rightPart逆序

AF FA
BCED  DECB

AF 1 BCED 22 DECB FA

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        String str = reader.readLine();
        String strlps = reader.readLine();
        char[] chars = str.toCharArray();
        char[] lps = strlps.toCharArray();
        char[] res = new char[2 * chars.length - lps.length];

        int charsL = 0;
        int charsR = chars.length - 1;
        int lpsL = 0;
        int lpsR = lps.length - 1;
        int resL = 0;
        int resR = res.length - 1;

        while (lpsL <= lpsR){
            int tmpL = charsL;
            int tmpR = charsR;
            while (chars[charsL] != lps[lpsL]){
                charsL ++;
            }
            while (chars[charsR] != lps[lpsR]){
                charsR --;
            }
            // lPart + rPart的逆序
            for(int i=tmpL;i<charsL;i++){
                res[resL++] = chars[i];
                res[resR--] = chars[i];
            }
            for(int i = tmpR; i > charsR; i--){
                res[resL++] = chars[i];
                res[resR--] = chars[i];
            }
            res[resL++] = lps[lpsL++];
            res[resR--] = lps[lpsR--];
            charsL ++;
            charsR --;
        }
        System.out.println(res);
    }

}
/*
A1BC22DE1F
1221

*/