# Longest Common Substring

jeongbeom4693

❗ LCS는 Longest Common Subsequence의 줄임말로, 공통 부분 문자열 중 가장 길이가 긴 문자열을 말합니다.

cldhfleks2

개요 주어지는 2개의 문자열의 서로 공통인 부분수열중 길이가 가장 긴것의 길이를 찾는 알고리즘이다. 이때의 부분수열은 연속되지않은 부분수열도 포함하여 LCS를 찾게된다. 이번에 소개할 LCS알고리즘을 사용하면 두 문자열의 길이 N, M에따른 O(N * M)만에 LCS를 찾을 수 있다. 작동원리 LCS알고리즘을 설명할때 자주쓰이는 두 문자열 'ACAYKP'...

emplam27

LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.