테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 새로운 과일 ======

===== 풀이 =====
  * [[ps:tutorial:lcs#Shortest common supersequence]] 문제. LCS를 찾고 나머지 글자들을 순서에 맞게 채워주면 된다. 시간복잡도는 O(nm/w).

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:string#longest_common_subseq|teflib.string.longest_common_subseq]]

{{tag>BOJ ps:problems:boj:골드_2}}