가장 긴 공통 부분 문자열의 방법이 맞습니까?

Question

나는 알고리즘을 찾았습니다. 가장 긴 공통 부분 문자열.일반적으로 다음을 사용하여 수행됩니다. dynamic programming, 크기의 2차원 배열 사용 mxn 어디 m 그리고 n 고려 중인 두 문자열의 길이입니다.

두 문자열에 대해 다음 행렬을 구성하겠습니다.

M[i][j] = 1 if s1[i]==s2[j] else 0.

예를 들어, 문자열이 다음과 같은 경우: abcxy 그리고 pqaabx

매트릭스는 다음과 같습니다:

    a b c x y
 p  0 0 0 0 0
 q  0 0 0 0 0
 a  1 0 0 0 0
 a  1 0 0 0 0
 b  0 1 0 0 0
 x  0 0 0 1 0

이제 나는 다음의 최대 연속 수열을 검색합니다. 1s는 왼쪽 위에서 오른쪽 아래 방향으로 있는 모든 대각선에 있습니다.

이 중 최대값이 답이 될 것입니다.

명시적으로 배열을 사용하지 않고도 위 작업을 수행할 수 있습니다.시간복잡도는 여전히 O(M*N).따라서 메모리가 필요하지 않습니다.

누구든지 내가 어디로 잘못 가고 있는지 알려줄 수 있습니까?

Answer 1

귀하의 방법이 정확합니다.증명을 위해 S1과 S2에 대한 가장 긴 공통 부분 문자열이 S1[i..j]와 S2[p..q]에서 나왔다고 가정합니다.이것은 s1 [i+k] = s2 [p+k]를 의미합니다.

이것들은 모두 (i,p)에서 시작하는 대각선에 있습니다.

동적 프로그래밍 솔루션은 동일한 작업을 수행하지만 테이블을 먼저 계산하고 대각선 경로를 통과하는 대신 대각선 부모와 일치 여부에 따라 테이블을 계산합니다.

편집됨

추가 메모리를 사용하는 Wikipedia 솔루션에 대한 귀하의 의견.이는 명확성을 위해서만 존재합니다.원칙적으로 Wikipedia 솔루션에서는 행렬의 두 행만 필요하며 현재 최대 개수를 하나의 변수로 유지합니다.이는 행렬의 모든 (i,j)번째 항목에 대해 정확합니다.

M(i,j) = 1 + M(i-1, j-1) (s1[i] == s2[j]인 경우)

보시다시피 현재 행 요소는 바로 위쪽 행의 요소에만 의존합니다.

Answer 2

알고리즘은 정확하지만 표준 DP 접근 방식은 두 번째 단계를 제거하고 솔루션을 더 간단하게 만듭니다.

부울 값을 표시한 다음 대각선을 스캔하여 가장 긴 시퀀스를 찾는 대신 행렬을 구축하면서 대각선 길이를 계산할 수 있습니다. 단 한 번의 패스만 필요합니다.

시간 및 공간 복잡도 측면에서 두 솔루션 모두 O(NxM)입니다.귀하의 솔루션은 비트 매트릭스 표현을 사용하면 일부 메모리를 절약할 수 있지만 다른 솔루션은 아마도 약간 더 빠를 것입니다.