2016-09-30 10 views
2

여러 문자열 (k> 2)에 대해 가장 긴 공통 부분 시퀀스 문제가 NP-Hard 인 이유를 이해하는 데 어려움을 겪고 있습니다. 길이 l1, l2의 두 문자열에 대한 LCS 문제는 O (l1 * l2) 시간으로 풀 수 있다는 것을 알고 있습니다. 제 질문은 한 번에 두 문자열의 LCS를 찾을 수없는 이유입니다. 예를 들어왜 여러 문자열에 대해 가장 긴 공통 하위 시퀀스가 ​​NP-Hard입니까?

LCS (abcd, ad, abc) = LCS (LCS (abcd, ad) abc) = a

이 알고리즘은 k 개의 문자열에 대해 O (k * Max_length^2)를 사용합니다. 이게 왜 틀린거야?

+0

첫 등호가 잘못되었습니다 : LCS (eeeabcd, eeead, abc)! = LCS (eCS, eeead), abc) 예 : – user1470500

+0

LCS (eeeabcd, eeead) = eeead, LCS (eeead, abc) = a ? – Kapil

답변

5

LCS (x, y, z) = LCS (x, LCS (y, z))는 일반적으로 사실이 아닙니다. 예를 들어

LCS (BB, aaabb, bbaaa) ​​= BB

LCS (BB, LCS (aaabb, bbaaa)) =의 LCS (BB, AAA) ≠ BB