Longest Common Subsequence1 [Algorithm] LCS (Longest Common Substring / Subsequence) 알고리즘 LCS란? LCS는 최장 공통 문자열(Lognest Common Substring) 또는 최장 공통 부분 수열(Longest Common Subsequence)을 의미한다. 전자는 연속된 문자열에 대한 것을 뜻하고 후자는 연속되지 않은 문자열이 포함될 수 있다. 최장 공통 문자열 (Longest Common Substring) 최장 공통 문자열을 구하는 과정은 다음과 같다. 문자열 A의 i번째 문자와 문자열 B의 j번째 문자를 비교한다. 두 문자가 같다면 ( A[i] == B[j] ) dp[i][j]에 dp[i-1][j-1] + 1을 대입한다. 두 문자가 다르다면 ( A[i] != B[j] ) dp[i][j]의 값을 0으로 설정한다. 과정중에 구한 최댓값이 최장 공통 문자열의 길이가 된다. 공통 문자열은.. 2022. 5. 1. 이전 1 다음
