LCS(Longest Common Subsequence) 알고리즘

LCS 알고리즘이란?

 

• LCS 알고리즘이란,
  최장 공통 부분 수열(Longest Common Subsequence)과
  최장 공통 부분 문자열(Longest Common Substring)가 존재한다.

• 최장 공통 부분 수열
  ABCDEFG
  ABCGEDF
  -> ABCEF로 길이가 5.

• 최장 공통 부분 문자열
  ABCDEFG
  ABCGEDF
  -> ABC로 길이가 3.

 

최장 공통 부분 문자열

 

STRING 1 : ABCDEFG
STRING 2 : ABCGEDF

조건문

if( j == 0 || i == 0 ) dp[i, j] = 0
if ( S1[i - 1] == S2[j - 1] )  dp[i, j] = dp[i - 1, j - 1] + 1
else dp[i, j] = max(dp[i - 1, j] , dp[i, j - 1])

 

 

출 처

Algoritms : https://algorithms.tutorialhorizon.com/dynamic-programming-longest-common-subsequence/