Longest Common Substring

최장공통문자열(Longest Common Substring - LCS)

들어가기에 앞서 LCS를 구별하도록 하자. 일반적으로 LCS라고 하면 최장공통부분수열(Longest Common Subsequence)을 뜻하지만, 최장공통 문자열(Longest Common Sustring)도 LCS라고 부르기도 한다. 둘의 차이점은 구하고자 하는 부분 문자열의 연속성이라고 할 수 있다. 이번 글에서는 최장공통 문자열(Longest Common Substring)에 대해서 먼저 알아보자 1. 개념 🦆 최장공통부분문자열(LCS)은 연속된 부분 문자열 중 가장 길이가 긴 문자열을 말한다. 2. 동작 방식 🐓 동작 방식은 DP를 이용한다. 문자열 A와 문자열 B가 주어졌다고 하자. 문자열 A와 문자열 B를 한 글자씩 비교한다. 비교하는 문자가 같다면 DP[i][j]는 DP[i-1][j-1] ..