LCS

태그

최장 공통 부분 문자열

알고리즘

LCS(Longest Common Substring)

•

최장 공통 부분 문자열이다.

•

DP  를 기반으로 한다.

•

Substring 은 연속된 부분 문자열을 확인한다.

첫번째로 해야 할 일은 dp 테이블을 생성하는 것이다. 이때 첫번째 행과 열은 항상 0 으로 맞춰준다.

테이블을 채우는 기준은 아래와 같다.

서로 같은 문자열이 오면 대각선(왼쪽 위)의 값 + 1 을 한다.

이는 공통 문자열은 연속되어야 하기 때문이다.

만들어진 테이블에서 최댓값을 찾으면 LCS 탐색이 종료된다.

•

최장 공통 부분 수열이다.

•

DP 를 기반으로 한다.

•

Subsequence 는 연속되지 않은 부분 문자열을 찾는다.

첫번째로 해야 할 일은 dp 테이블을 생성하는 것이다. 이때 첫번째 행과 열은 항상 0 으로 맞춰준다.

테이블을 채우는 기준은 아래와 같다.

•

서로 다른 문자열이 오면 위, 왼쪽 값을 비교하여 더 큰 값을 넣는다.

•

서로 같은 문자열이 오면 대각선(왼쪽 위)의 값 + 1 을 한다.

이전과 서로 다른 문자열 부분에서 차이점을 보이는 이유는 공통 부분 수열은 연속될 필요가 없기 때문이다. 만들어진 테이블에서 최댓값을 찾으면 LCS 탐색이 종료된다.

이렇게 만들어진 테이블에서 결과를 찾는과정은 다음과 같다.

LCS 배열의 가장 마지막 값에서 시작해서 위 / 아래 중 현재 값과 같은 값을 찾는다. 

값을 찾았다면 해당 값으로 이동한다. 그 후 왼쪽과 위쪽값 중 현재와 같은 값을 찾는다.

2.1. 현재와 같은 값이 없다면 대각선으로 이동한다. 그 후 다시 2 번 과정을 반복한다.

2.2. 값을 찾았다면 해당 값으로 이동하여 2 번 과정을 반복한다.

0 으로 이동하면 종료하고, 배열을 뒤집는다.