Longest Common Substring 문제는 두 문자열에 공통으로 존재하는 가장 긴 연속된 문자열을 찾는 문제입니다.
예:
ABABC
BABCA
두 문자열에 연속해서 존재하는 가장 긴 부분은:
BABC
이므로 길이는 4입니다.
Substring의 핵심은 연속성
문자열:
ABCDE
에서 다음은 Substring입니다.
ABC
BCD
DE
하지만 ACE는 문자가 연속하지 않기 때문에 Substring이 아닙니다.
Dynamic Programming
다음을 정의합니다.
dp[i][j]
이는 a[i - 1]와 b[j - 1]에서 정확히 끝나는 공통 Substring의 길이입니다.
두 문자가 같으면:
dp[i][j] = dp[i - 1][j - 1] + 1
다르면:
dp[i][j] = 0
Mismatch에서 0으로 초기화하는 이유는 Substring이 반드시 연속되어야 하기 때문입니다.
예제 테이블
B A B C A
A 0 1 0 0 1
B 1 0 2 0 0
A 0 2 0 0 1
B 1 0 3 0 0
C 0 0 0 4 0
가장 큰 값은 4이며 BABC를 의미합니다.
TypeScript 구현
function longestCommonSubstring(
a: string,
b: string
): string {
const dp = Array.from(
{ length: a.length + 1 },
() => new Array(b.length + 1).fill(0)
);
let maxLength = 0;
let endIndex = 0;
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endIndex = i;
}
}
}
}
return a.slice(endIndex - maxLength, endIndex);
}
복잡도
문자열 길이를 각각 n, m이라고 하면:
Time Complexity: O(n × m)
Space Complexity: O(n × m)
이전 Row만 유지하면 공간을:
O(min(n, m))
까지 최적화할 수 있습니다.
Longest Common Substring과 LCS 차이
Substring은 문자가 연속해야 합니다.
Subsequence는 문자가 떨어져 있어도 순서만 유지되면 됩니다.
예:
ABCDEF
ACEF
ACEF는 Common Subsequence가 될 수 있지만 첫 문자열의 Substring은 아닙니다.
DP에서도 중요한 차이가 있습니다.
Longest Common Substring에서 mismatch가 발생하면:
dp[i][j] = 0
입니다.
실제 활용
이 개념은 다음과 같은 곳에서 활용할 수 있습니다.
- 문자열 유사도 분석
- CRM 데이터 중복 탐지
- Data Cleaning
- DNA Sequence 비교
- 문서 및 버전 비교
- Log Pattern 분석
실제 중복 탐지 시스템에서는 Levenshtein Distance, Email, Phone, Token Similarity 등 다른 Signal과 함께 사용하는 것이 좋습니다.
여러 정답
같은 최대 길이를 가진 Substring이 여러 개 존재할 수도 있습니다.
abcXYZ123
abcABC123
여기에서는 abc와 123 모두 길이 3입니다.
기술 면접 핵심
면접에서는 다음을 설명할 수 있어야 합니다.
- Substring은 연속되어야 한다.
dp[i][j]가 무엇을 의미하는가.- mismatch에서 왜 0으로 초기화하는가.
maxLength를 따로 유지해야 하는 이유.- 시간 복잡도
O(n × m).
정리
Longest Common Substring의 핵심 관계는 다음과 같습니다.
Match → dp[i - 1][j - 1] + 1
Mismatch → 0
즉, 하나라도 문자가 다르면 현재 연속 Match는 즉시 끊어집니다.