3 개의 문자열 중에서 가장 긴 공통 서브 시퀀스

Question

2 개의 문자열 중에서 가장 긴 공통 서브 시퀀스를 찾기 위해 동적 프로그래밍 솔루션을 구현했습니다. 이 알고리즘을 일반화하여 3 개의 문자열 중에서 LCS를 찾는 방법이 있지만 내 연구에서는이 방법에 대한 정보를 찾지 못했습니다. 어떤 도움을 주시면 감사하겠습니다.

Answer 1

반복 관계를 일반화합니다.

세를 들어 문자열 :

dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if A[i] = B[j] = C[k] 
       max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise 

대답은 비슷한 질문 here에서 가져온 것입니다.

Answer 2

2 개의 문자열 A와 B의 LCS (Longest Common Subsequence)를 찾으려면 게시 한 링크와 같이 대각선으로 2 차원 배열을 탐색 할 수 있습니다. 배열의 모든 요소는 하위 문자열 A '및 B'의 LCS를 찾는 문제에 해당합니다 (A는 행 번호로 자르고 B는 열 번호로 자름). 이 문제는 배열의 모든 요소 값을 계산하여 해결할 수 있습니다. 배열 요소의 값을 계산할 때 주어진 값을 계산하는 데 필요한 모든 하위 문제가 이미 해결되었음을 확신해야합니다. 그래서 2 차원 배열을 대각선으로 가로 지르는 것입니다.

이 해결 방법은 N 개의 문자열 사이에서 가장 긴 공통 하위 시퀀스를 찾을 수 있도록 확장 할 수 있지만 N 개의 차원 배열을 반복하는 일반적인 방법이 필요합니다. 모든 하위 문제에 대한 해결책이 필요한 경우에만 요소에 도달합니다. 해결되었습니다.

N 차원 배열을 특별한 순서로 반복하는 대신 재귀 적으로 문제를 해결할 수도 있습니다. 재귀를 사용하면 중간 지점 솔루션을 저장하는 것이 중요합니다. 많은 지점에서 동일한 중간 솔루션이 필요하기 때문입니다. 나는 이것을 수행하는 C#의 작은 예제를 작성했다 :

string lcs(string[] strings) 
{ 
    if (strings.Length == 0) 
     return ""; 
    if (strings.Length == 1) 
     return strings[0]; 
    int max = -1; 
    int cacheSize = 1; 
    for (int i = 0; i < strings.Length; i++) 
    { 
     cacheSize *= strings[i].Length; 
     if (strings[i].Length > max) 
      max = strings[i].Length; 
    } 
    string[] cache = new string[cacheSize]; 
    int[] indexes = new int[strings.Length]; 
    for (int i = 0; i < indexes.Length; i++) 
     indexes[i] = strings[i].Length - 1; 
    return lcsBack(strings, indexes, cache); 
} 
string lcsBack(string[] strings, int[] indexes, string[] cache) 
{ 
    for (int i = 0; i < indexes.Length; i++) 
     if (indexes[i] == -1) 
      return ""; 
    bool match = true; 
    for (int i = 1; i < indexes.Length; i++) 
    { 
     if (strings[0][indexes[0]] != strings[i][indexes[i]]) 
     { 
      match = false; 
      break; 
     } 
    } 
    if (match) 
    { 
     int[] newIndexes = new int[indexes.Length]; 
     for (int i = 0; i < indexes.Length; i++) 
      newIndexes[i] = indexes[i] - 1; 
     string result = lcsBack(strings, newIndexes, cache) + strings[0][indexes[0]]; 
     cache[calcCachePos(indexes, strings)] = result; 
     return result; 
    } 
    else 
    { 
     string[] subStrings = new string[strings.Length]; 
     for (int i = 0; i < strings.Length; i++) 
     { 
      if (indexes[i] <= 0) 
       subStrings[i] = ""; 
      else 
      { 
       int[] newIndexes = new int[indexes.Length]; 
       for (int j = 0; j < indexes.Length; j++) 
        newIndexes[j] = indexes[j]; 
       newIndexes[i]--; 
       int cachePos = calcCachePos(newIndexes, strings); 
       if (cache[cachePos] == null) 
        subStrings[i] = lcsBack(strings, newIndexes, cache); 
       else 
        subStrings[i] = cache[cachePos]; 
      } 
     } 
     string longestString = ""; 
     int longestLength = 0; 
     for (int i = 0; i < subStrings.Length; i++) 
     { 
      if (subStrings[i].Length > longestLength) 
      { 
       longestString = subStrings[i]; 
       longestLength = longestString.Length; 
      } 
     } 
     cache[calcCachePos(indexes, strings)] = longestString; 
     return longestString; 
    } 
} 
int calcCachePos(int[] indexes, string[] strings) 
{ 
    int factor = 1; 
    int pos = 0; 
    for (int i = 0; i < indexes.Length; i++) 
    { 
     pos += indexes[i] * factor; 
     factor *= strings[i].Length; 
    } 
    return pos; 
} 

내 코드 예제는 더 이상 최적화 될 수있다. 캐시되는 문자열의 대부분은 중복이며 일부는 추가 된 하나의 문자 만 추가하여 중복됩니다. 이렇게하면 입력 문자열이 커질 때 필요한 것보다 많은 공간이 사용됩니다. 입력에

"666222054263314443712", "5432127413542377777"는 LCS 반환 "6664664565464057425"

정말 대신 2의 3 문자열 일 변경 "54442"