添加最少的字符让字符串变成回文串（2）

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s1, s2;
    cin>>s1>>s2;
    int n=s1.length(), m=s2.length(), t=2*n-m;
    string s(t, '\0');
    int i=0, j=n-1, k=0, l=0;
    while(i<=j){
        if(s1[i]!=s2[k]){
            s[l] = s1[i];
            s[t-l-1] = s1[i++];
        }else if(s1[j]!=s2[k]){
            s[l] = s1[j];
            s[t-l-1] = s1[j--];
        }else{
            s[l] = s1[j];
            s[t-l-1] = s1[j--];
            i++;
            k++;
        }
        l++;
    }
    cout<<s<<endl;
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXLEN 5001

int main(void) {
    char str[MAXLEN], strips[MAXLEN], *res;
    scanf("%s%s", str, strips);
    int n = strlen(str);
    int m = strlen(strips);
    res = (char *) malloc(2 * n - m + 1);
    res[2 * n - m] = '\0';
    int l = 0, r = 2 * n - m - 1;
    int ll = 0, lr = 0, rl = n - 1, rr = n - 1;
    int i = 0, j = m - 1;
    while (i <= j) {
        while (str[lr] != strips[i]) lr++;
        while (str[rl] != strips[j]) rl--;
        while (ll < lr) {
            res[l++] = str[ll];
            res[r--] = str[ll++];
        }
        while (rl < rr) {
            res[l++] = str[rr];
            res[r--] = str[rr--];
        }
        ll = ++lr;
        rr = --rl;
        res[l++] = strips[i++];
        res[r--] = strips[j--];
    }
    printf("%s\n", res);
    free(res);
    return 0;
}

# 首先找到最长回文串元素所在位置
def find_indices(string, strlps):
    indices = []
    j = 0
    for i, c in enumerate(string):
        if j < len(strlps) and c == strlps[j]:
            indices.append(i)
            j += 1
    return indices

# 按照最长回文串元素分割字符串
# 如 A1B21C 会被分割成 ['A', '1', 'B', '2', '', '1', 'C']
def split_palindrom(string, strlps):
    substrs = []
    indices = find_indices(string, strlps)
    for i in range(len(indices) - 1):
        substrs.extend([string[indices[i] + 1: indices[i + 1]], string[indices[i + 1]]])
    substrs = [string[:indices[0]], string[indices[0]]] + substrs + [string[indices[-1] + 1:]]
    return substrs

# 找两个回文串的最短公共回文串（类似于最小公倍数）
def get_palindrom_string(s1, s2):
    if s1 == s2[::-1]:
        return s1, s2
    i = j = 0
    while i < len(s1) and len(s2) - 1 - i > -1 and s1[i] == s2[len(s2) - 1 - i]:
        i += 1
    while j < len(s2) and len(s1) - 1 - i > -1 and s2[j] == s1[len(s1) - 1 - j]:
        j += 1
    unmatch_part_s1 = s1[i: len(s1) - j]
    unmatch_part_s2 = s2[j: len(s2) - i]
    new_part_s1 = unmatch_part_s1 + unmatch_part_s2[::-1]
    new_part_s2 = unmatch_part_s2 + unmatch_part_s1[::-1]
    return s1[:i] + new_part_s1 + s1[len(s1) - j:], s2[:j] + new_part_s2 + s2[len(s2) - i:]

def solve(string, strlps):
    strings = split_palindrom(string, strlps)
    i = 0
    j = len(strings) - 1
    while i < j:
        strings[i], strings[j] = get_palindrom_string(strings[i], strings[j])
        i += 1
        j -= 1
    return "".join(strings)

if __name__ == "__main__":
    string = input()
    strlps = input()
    print(solve(string, strlps))

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;


public class Main {
    private static String getPalindrome(String str, String strlps) {
        if (str == null || str.equals("")) {
            return "";
        }

        char[] chas = str.toCharArray();
        char[] lps = strlps.toCharArray();
        int strLen = chas.length;
        int lpsLen = lps.length;
        int resLen = 2 * strLen - lpsLen;
        char[] res = new char[resLen];
        int chasl = 0;
        int chasr = strLen - 1;
        int lpsIdx = 0;
        int resIdx = 0;

        while (chasl <= chasr) {
            if (chas[chasl] != lps[lpsIdx]) {
                res[resIdx] = chas[chasl];
                res[resLen - resIdx - 1] = chas[chasl++];
            } else if (chas[chasr] != lps[lpsIdx]) {
                res[resIdx] = chas[chasr];
                res[resLen - resIdx - 1] = chas[chasr--];
            } else {
                res[resIdx] = lps[lpsIdx];
                res[resLen - resIdx - 1] = lps[lpsIdx];
                chasl++;
                chasr--;
                lpsIdx++;
            }
            resIdx++;
        }

        return new String(res);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String strlps = br.readLine();
        System.out.println(getPalindrome(str, strlps));
    }
}