• Shortest common supersequence 문제. LCS를 찾고 나머지 글자들을 순서에 맞게 채워주면 된다. 시간복잡도는 O(nm/w).

"""Solution code for "BOJ 6574. 새로운 과일".

- Problem link: https://www.acmicpc.net/problem/6574
- Solution link: http://www.teferi.net/ps/problems/boj/6574

Tags: [lcs]
"""

import sys
from teflib import psutils
from teflib import string


def shortest_common_supersequence(str_a, str_b):
    ret = []
    a_ind = b_ind = 0
    for c in string.longest_common_subseq(str_a, str_b):
        a_prev, a_ind = a_ind, str_a.find(c, a_ind) + 1
        b_prev, b_ind = b_ind, str_b.find(c, b_ind) + 1
        ret.append(str_a[a_prev : a_ind - 1])
        ret.append(str_b[b_prev:b_ind])
    ret.append(str_a[a_ind:])
    ret.append(str_b[b_ind:])
    return ''.join(ret)


@psutils.run_until_eof
def main():
    str_a, str_b = sys.stdin.readline().split()
    print(shortest_common_supersequence(str_a, str_b))


if __name__ == '__main__':
    main()

• Dependency: teflib.string.longest_common_subseq