LCS, longest common subsequence vs longest common substring

• 여기에서는 두가지를 다룬다.
  • longest common subsequence
  • longest common substring
  • 두 개념의 약어는 모두 LCS... 이다.
    • 두 개념이 헷갈릴 수 있어서... 같이 정리해본다.
• longest common subsequence
  • 한국어로는 최장 공통 부분 수열이라고 한다.
  • 최장 공통 부분 수열은? 두 문자열에 공통적으로 존재하는 가장 긴 부분 수열이다.
    • 여기서 주목할 점은 부분 수열이니 연속된 것이 아니라는 점이다.

  • 예제를 들어 설명해본다.

    1. 두개의 문자열이 있다. : bcdb, abcbdab   2. 두 문자열의 최장 공통 부분 수열을 구해본다. 그림으로 표시해보면...    bc d b abcbdab   3. 위에 보면 공통으로 존재하는 부분 수열이 {b,c,d,b}가 된다.

  • 아주 간단해보인다.

    • 하지만, 이 알고리즘은 diff 알고리즘의 근간이 된다.
      • 그만큼 중요한 알고리즘이며, 그리고... 문제를 풀때는... 간단하지도 않다. 
  • 문제를 푸는 방법
    

    • 식으로 정리하면
      

    • 최장 공통 부분 수열과 관련된 알고리즘으로는... '최장 공통 부분 수열의 길이를 구하는 로직'이다.

      예전에 풀었던 문제중 최장 공통 수열의 길이를 구하는 문제에 대한 알고리즘이다. 1. len(a) + 1 x len(b) +1 table을 생성한다. 2. lcs_tbl[i,j] 값은 1) a[i] == b[j] 을 때는 lcs_tbl[i-1][j-1] + 1                      2) a[i] != b[j] 아닐 때는 lcs_tbl[i-1, j] 또는 lcs_tbl[i, j-1] 중에서 큰 값을 저장한다.                          * 이는 공통 문자의 경우 수열의 길이가 증가함을 의미하고                            공통 문자가 아닐 경우에는 이전 결과 중 공통 부분 수열이 긴 것을 가져오는 것을 의미한다. 3. 이렇게 했을 때, lcs[len(a) + 1][len(b) + 1]의 값이 최장 공통 부분 수열의 크기이다. 4. 문제의 조건에 따라 최장 공통 부분 수열 중 하나를 출력하기 위해서는 마지막 부터 backtracking 해서 값을 구한다.

    • 테이블을 만든다. 아래처럼... 위 식을 참고해서...(이 부분은 나중에 시간나면 정리하는 것으로...한다)

      	0	a	b	c	b	d	a	b
      0	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
      b	Ø	Ø	b	b	b	b	b	b
      c	Ø
      d	Ø
      b	Ø

  • 참고 링크 : http://ko.wikipedia.org/wiki/최장_공통_부분_수열

 

• longest common substring

  • 최장 공통 부분 문자열

    • 최장 공통 부분 문자열의 가장 큰 특징은!! 연속된 문자열이라는 점이다.
      • 이 부분은 longest common subsequence와 다른 점이다.

    • 예제를 들어 설명해보면...

      1. 두개의 문자열이 있다. : bcdb, abcbdab   2. 두 문자열의 최장 공통 부분 문자열을 구해본다. 그림으로 표시해보면...    bcdb abcbdab   3. 여기서 최장 공통 부분 문자열은 bc가 된다.

    • longest common substring을 찾기 위해서 주로 suffix tree를 사용한다.(wiki를 보니 Dynamic programming으로 해결하는 방법도 있었다.)

      • suffix tree는 string의 모든 substirng을 tree 형태로 나타낸 것이다.
        • suffix tree를 통해 부분 문자열에 대한 연산을 할 수 있다.
  • 참고 링크
    • longest common substring wiki : http://en.wikipedia.org/wiki/Longest_common_substring_problem
    • suffix tree wiki : http://en.wikipedia.org/wiki/Suffix_tree
    • suffix array에 대한 설명 : http://blog.sbnet21.com/1755, http://crack-tech-interview.com/2014/04/09/suffix-tree-%EC%99%80-%EC%9D%B4%EC%9D%98-%EA%B0%84%EB%8B%A8%ED%95%9C-application/
• 사설...
• 문제를 어떻게 풀 수 있는지... 그리고 suffix tree를 어떤 형태로 구현하고, 또 사용할 수 있는지에 대해서도 정리하고 싶었지만... 시간 관계상 이정도 선에서 마무리한다.
• 다음에 기회가 된다면, 좀 더 정리할 것이다.

본 글은 회사 위키에 작성한 글과 동일합니다.