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)를 사용합니다. 이게 왜 틀린거야?
첫 등호가 잘못되었습니다 : LCS (eeeabcd, eeead, abc)! = LCS (eCS, eeead), abc) 예 : – user1470500
LCS (eeeabcd, eeead) = eeead, LCS (eeead, abc) = a ? – Kapil