Computer >> 컴퓨터 >  >> 프로그래밍 >> JavaScript

JavaScript로 두 문자열 사이의 가장 긴 공통 연속 부분 문자열 찾기

두 개의 문자열을 입력받아, 두 문자열 모두에 공통으로 등장하는 가장 긴 연속 부분 문자열(Longest Common Substring)을 찾아 반환하는 JavaScript 함수를 작성해야 합니다. 여기서 중요한 점은 부분 문자열이 반드시 원본 문자열에서 연속된 형태로 나타나야 한다는 것입니다.

문제 예시

예를 들어, 입력 문자열이 다음과 같다고 가정해 보겠습니다.

const str1 = 'ABABC';
const str2 = 'BABCA';

이 경우 함수가 반환해야 할 결과는 다음과 같습니다.

const output = 'BABC';

'BABC'는 str1의 인덱스 1부터, str2의 인덱스 0부터 각각 연속적으로 등장하며, 두 문자열이 공유하는 가장 긴 공통 구간입니다.

접근 방식: 동적 계획법(DP)

이 문제는 동적 계획법(Dynamic Programming)을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 두 문자열의 길이를 기준으로 2차원 테이블(arr)을 생성합니다.
  • arr[i][j]에는 "str2의 i번째 문자와 str1의 j번째 문자가 일치할 때, 해당 위치에서 끝나는 공통 연속 부분 문자열의 길이"를 저장합니다.
  • 두 문자가 같으면 arr[i][j] = arr[i-1][j-1] + 1, 다르면 0으로 설정합니다.
  • 테이블을 채우는 동안 최대 길이(len)와 그 끝 위치(row, col)를 함께 기록합니다.
  • 마지막에 기록해 둔 위치에서 거꾸로 역추적하여 실제 공통 문자열을 조립합니다.

구현 코드

const str1 = 'ABABC';
const str2 = 'BABCA';
const findCommon = (str1 = '', str2 = '') => {
    const s1 = [...str1];
    const s2 = [...str2];
    const arr = Array(s2.length + 1).fill(null).map(() => {
        return Array(s1.length + 1).fill(null);
    });
    for (let j = 0; j <= s1.length; j += 1) {
        arr[0][j] = 0;
    }
    for (let i = 0; i <= s2.length; i += 1) {
        arr[i][0] = 0;
    }
    let len = 0;
    let col = 0;
    let row = 0;
    for (let i = 1; i <= s2.length; i += 1) {
        for (let j = 1; j <= s1.length; j += 1) {
            if (s1[j - 1] === s2[i - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            }
            else {
                arr[i][j] = 0;
            }
            if (arr[i][j] > len) {
                len = arr[i][j];
                col = j;
                row = i;
            }
        }
    }
    if (len === 0) {
        return '';
    }
    let res = '';
    while (arr[row][col] > 0) {
        res = s1[col - 1] + res;
        row -= 1;
        col -= 1;
    }
    return res;
};
console.log(findCommon(str1, str2));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

BABC

코드 동작 원리 자세히 살펴보기

  1. 테이블 초기화: 스프레드 연산자([...str1], [...str2])로 문자열을 문자 배열로 변환한 뒤, (s2.length + 1) × (s1.length + 1) 크기의 2차원 배열을 만들고 첫 번째 행과 열을 0으로 채웁니다. 이는 "빈 문자열과는 어떤 공통 부분도 존재하지 않는다"는 의미입니다.
  2. 테이블 채우기: 두 문자가 일치하면 왼쪽 대각선 값(arr[i-1][j-1])에 1을 더하고, 일치하지 않으면 0으로 초기화합니다. 불일치 시 값을 0으로 되돌리는 것이 바로 "연속성"을 보장하는 핵심 장치입니다.
  3. 최댓값 추적: 테이블을 채우는 과정에서 지금까지 발견한 최대 길이(len)와 해당 값이 끝나는 위치(row, col)를 저장해 둡니다.
  4. 역추적: 최대 길이 위치에서 arr[row][col] > 0인 동안 대각선 위쪽으로 이동하며 문자를 하나씩 앞에 붙여, 최종 결과 문자열을 완성합니다.

복잡도 분석

  • 시간 복잡도: O(m × n) — m과 n은 각각 두 문자열의 길이입니다.
  • 공간 복잡도: O(m × n) — 2차원 DP 테이블을 사용합니다. 필요하다면 직전 행만 유지하는 방식으로 O(min(m, n))까지 최적화할 수 있습니다.