LCS O(NlogN)만에 푸는법 알려줘

[익명(223.62)]

ㅇㅇ

[0xrgb(0xrgb)]

일반적인 LCS는 O(N^2)이 최선이라 안댐

[0xrgb(0xrgb)]

조건이 달려있으면 되는데 예를 들어서 양쪽이 1~N으로 이루어진 순열이면 LIS 응용해서 가능

[0xrgb(0xrgb)]

알파벳 사이즈가 정해져있으면 Method of Four Russians 라고 방법이 있는데 O(N log N)은 아니였던걸로 기억

[익명(223.62)]

ㄱㅅㄱㅅ LIS꼴만 되구나