알고리즘 1000 개 노크 #2. Longest common substrings

Problem

与えられた２つの文字列に対し, 共通で持つ部分文字列の最大長を求めよ.
例) "abcdefg" と "cdeg" が与えられたとして, 最大の部分文字列は "cde" なので答えは３.

Solution

DP (다이나믹 프로그래밍) 중에서 고전적인 문제입니다.

두 문자열을 S1과 S2, 각각의 길이를 M, N으로 설정합니다.
총당으로 S1에서 모든 부분 문자열을 추출하고, 그것들이 S2에 포함되어 있는지를 하나씩 체크하는 것도 풀 수 있지만, 계산량은 O(M^2*N)가 되어 버려 네.

효율적으로 풀기 위해서, 배열 m[M][N] 을 준비해 m[i][j] 에 S1[i] 와 S2[j] 가 각각 공통의 부분 캐릭터 라인의 몇 문자째에 해당하는지를 저장합니다. (공통 부분 문자열에 포함되어 있지 않으면 0을 넣습니다)



위의 예를 보면, S1[3]도 S2[1]도 'd', 그리고 and m[2][0] = 1이므로 m[3][1] = 2가 됩니다. 즉, S1[3 ] and S2 [1]은 부분 문자열의 두 번째 문자 (앞의 문자가 첫 번째 문자이기 때문에)입니다.
이것을 일반화하고, m[i][j] 는 S1[i] =S2[j] 라면 m[i-1][j-1]+1, 그렇지 않으면 0과 값을 구해 나가는 것 할 수 있습니다.

이것이 소위 상향식 동적 프로그래밍입니다.

algorithms_dp_longest_common_substring.py

def LCS(s1, s2):
    if not s1 or not s2:
        return 0

    len1, len2 = len(s1), len(s2)

    # memorization
    m = []
    for i in range(len1):
        m.append([0]*len2) #m[len1][len2]

    lcs = 0

    # set 1st index value
    for i, ch in enumerate(s1):
        if ch == s2[0]:
            m[i][0] = 1
            lcs = 1
    for i, ch in enumerate(s2):
        if ch == s1[0]:
            m[0][i] = 1
            lcs = 1

    # m[i][j] stands for s1[i] and s2[j]
    # is the m[i][j] th bit of a common substring
    for i in range(1, len1):
        for j in range(1, len2):
            if s1[i] == s2[j]:
                m[i][j] = m[i-1][j-1] + 1
                lcs = max(m[i][j], lcs)
            else:
                m[i][j] = 0
    return lcs

이 경우 계산량과 공간 비용은 O (MN)입니다.

Jave 버전의 코드는 여기 :

algorithms_dp_longest_common_substring.java

public class Solution
{
  public static int LCS(String s1, String s2) {
    int l1 = s1.length();
    int l2 = s2.length();
    if (l1 == 0 || l2 == 0) return 0; // no common strings

    // memorization
    int[][] m = new int[l1][l2];
    int maxLen = 0;

    // set 1st index value
    for (int i = 0; i < l1; i++) {
      if (s1.charAt(i) == s2.charAt(0)) {
        m[i][0] = 1;
        maxLen = 1;
      } else m[i][0] = 0;
    }
    for (int i = 0; i < l2; i++) {
      if (s2.charAt(i) == s1.charAt(0)) {
        m[0][i] = 1;
        maxLen = 1;
      } else m[0][i] = 0;
    }

    // m[i][j] stands for s1.charAt(i) and s2.charAt(j)
    // is the m[i][j] th bit of a common substring
    for (int i = 1; i < l1; i++) {
      for (int j = 1; j < l2; j++) {
        if (s1.charAt(i) != s2.charAt(j)) m[i][j] = 0;
        else {
          m[i][j] = m[i-1][j-1] + 1;
          maxLen = (m[i][j] > maxLen)? m[i][j] : maxLen;
        }
      }
    }
    return maxLen;
  }
}