Longest Common Subsequence Algorithm

Longest Common Subsequence Algorithm 은 두 문자열이 공통으로 구성하는 단어 나열 패턴 중 제일 긴 것을 찾는 Algorithm이다.

Subsequence

공통으로 구성되는 단어 나열 패턴이라는 점에서 헷갈리는 부분이 생길 수 있다.

http://twinw.tistory.com/126 에서 좋은 예제를 들어서 그 내용을 가져와서 설명해보면,

IamHungry에서 mHung 는 모든 단어가 연속되면서 IamHungry에 포함 된다. 이러한 것을 Substring이라고 한다.

IamHungry에서 mugry 는 모든 단어가 연속되지 않지만, 단어의 나열 순서가 IamHungry의 단어 나열 순서와 일치한다. 이러한 것을 Subsequence이라고 한다.

Substring은 Subsequence보다 더 구체적인 개념(부분집합)이라고 볼 수 있다.

Solve : Dynamic Programming

Dynamic Programming의 기본은 하나의 문제를 여러개의 문제로 쪼갠뒤, 그 문제를 하나씩 풀고, 그 결과값을 다시 이용해서 다음문제를 풀어가는 방법이다. 이 과정에서 반복되어 사용되어 지는 문제의 값을 저장해 두었다가, 다시 사용하여 계산의 효율성을 올리는 것이다.

LCS문제를 간단하게 문제를 생각 해보자.
특정 문자열 2개의 LCS 값을 안다고 가정 했을때, 한 문자열에 한 단어만 추가한 것들의 LCS를 구하는 것이라면, 이미 아는 두개 문자열의 LCS값에다가, 추가되는 문자들이 만들어 내는 케이스만 추가 하면 된다.

이를 이용하여 한개의 문자열을 고정 값으로 놓고, 다른 한개의 문자열을 한단어씩 추가하며 LCS를 구하는 문제로 바꾸어 볼 수 있다.

한문자를 추가 하였을 때, 그 값의 고정된 문자열의 특정 문자와 일치 한다면, 그 이전 까지 구했던 LCS에 1을 더하면 된다. 만약 특정 위치의 문자와 일치 하지 않으면, 추가된 문자를 이용하여 고정 문자열의 전단계와 구한 LCS 값과, 이번 문자열을 사용 하지 않은 LCS 값 중 더 큰 값으로 LCS 값을 구하면 된다. 간단하게는 더 이득이 되는쪽으로 구해진 LCS 값을 사용 하면 된다.

코드로 구성 하면 다음과 같다.

package main

import "fmt"

func lcs(s1 string, s2 string) (int) {
    result := make([][]int, len(s1)+1)
    for i := range result {
        result[i] = make([]int, len(s2)+1)
    }

    for i := 1; i <= len(s1); i++ {
        for j := 1; j <= len(s2); j++ {
            if s1[i-1] == s2[j-1] {
                result[i][j] = result[i-1][j-1] + 1
            } else {
                result[i][j] = max(result[i-1][j], result[i][j-1])
            }
        }
    }

    return result[len(s1)][len(s2)]
}

func max(i1 int, i2 int) (int) {
    if i1 >= i2 {
        return i1
    } else {
        return i2
    }
}

func main() {
    s1 := "ABCDAA"
    s2 := "BACDAA"

    fmt.Println(lcs(s1, s2))
}

https://github.com/younseunghyun/lcs-go