LCS

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

제일 좋은 글. 정말 이해하기 쉽게 설명해주셨다.

 

 

문자열 기준으로, 최장 공통 문자열, 혹은 최장 공통 '부분'문자열로 해석할 수 있다.

 

그냥 최장공통문자열이면

 

ABCDEF

GBCDFE 

 

 두 문자열이 있을 때, 두 문자열의 최장공통문자열은 BCD 이다. 즉, 연속되어야 한다. 

 

하지만 최장 공통'부분'문자열이라면 연속될 필요 없다.

마찬가지로 ABCDEF와 GBCDFE가 있을 때, 두 문자열의 최장공통부분문자열은

 

BCDE 혹은 BCDF 이다. 즉, 최대길이는 4이고 문자열자체는 여러개가 나올 수 있다.

BCD는 연속되지만 E랑 F는 연속된게 아닌걸 알 수 있다.

 

구하는건 결국 DP이다. 점화식이 필요한데 일단 '최장공통문자열'은 매우 쉽다.

 

그냥 첫번째 문자열 하나씩 기준잡고 두번째 문자열 처음부터 끝까지 2중 반복문을 돌린다.

각각을 스트링 A,B라 했을 때,  A[i]와 B[j]가 같으면 dp[i][j] = dp[i-1][j-1] + 1로 dp테이블을 업데이트해주면 되고, 다르면은 

dp[i][j] = 0값 넣어주면 끝이다. 생각보다 매우 쉽다.

 

 

그러면 최장공통'부분'문자열이면?

 

즉 ABCDEF와 GBCDFE가 있을 때, BCDE or BCDF를 구하려면?

 

마찬가지로 반복문을 돌건데, 같을 때는 위 점화식과 똑같고, 다를때만 좀 달라진다.

위같은경우 다르다면 0을 넣었는데, 이번엔 max(dp[i-1][j], dp[i][j-1])값을 넣어주면 된다.

그러면 끝;;

 

 

 

단순히 길이가 아니라 문자열까지 구하려면 어떻게해야할까.

일단 위의 과정을 거쳐서 dp테이블을 미리 업데이트 시켜놔야한다.

해당 dp테이블을 이용해서 문자열을 구성한다.

n,m번째 인덱스부터 시작한다 가정한다. n은 s1.size()이고 m은 s2.size() 이다. 

초기에 dp테이블 업데이트과정에서 i를 s1으로 잡고 j를 s2로 잡았으니  dp[s1.size()][s2.size()] 부터 시작해야 한다.

 

1. dp[i-1][j] or dp[i][j-1]  두곳을 순서대로 탐색한다. 순서는 자기 맘대로다. 대신 그거에 따라 값은 달라지긴한다.(길이는 같지만) 탐색했을 때 현재값인 dp[i][j]랑 같다면 그대로 해당 인덱스로 이동한다.

 만약! 두 곳다 dp[i][j]와 같은 값이 없으면 dp[i-1][j-1]로 이동하고 dp[i][j]값을 answer문자열에 push_back해주면 된다.

 

이걸 계속 반복하면 된다. 실제 결과문자열에 값을 누적하는 과정은 dp[i-1][j-1]로 이동할 때인것만 알면된다.