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

# 首先找到最长回文串元素所在位置
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))