[주제 제안] Longest Common Subsequence

[cloneot]

주제 이름

• Longest Common Sequence

주제 소개 (관련 자료 링크 포함)

문자열 a, b가 있을 때,

1. LCS 역추적을 공간복잡도 O(|a|)로 하는 방법 (Hirschberg's algorithm)
   https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm
   https://koosaga.com/243
2. |a|<=100, |b|<=100만 일 때, LCS 구하는 방법 (O(|a|^2 log |b|)가 있다고 함)
3. |a|, |b| <= 5만 일 때, LCS 구하는 방법 (http://www.secmem.org/blog/2019/09/12/lcs-with-bitset/)

등 LCS와 관련된 것들

대략적인 난이도

• solved 기준 1번은 다이아3
• solved 기준 3번은 루비5

관련 문제 링크

• https://www.acmicpc.net/problem/18438 (1번, LCS 5)
• https://www.acmicpc.net/problem/18439 (3번, LCS 6)