[JS][백준]5582_공통 부분 문자열

문제 번호

5582번: 공통 부분 문자열

 

 

알고리즘 분류

DP

 

문제 풀이

 2차원 배열을 사용해서 공통 부분 문자열을 찾는 문제이다. 공통 부분 문자열은 연속된 문자열이다.

 

 해당 문제는 아래의 블로그에 나온 설명이 도움이 많이 되었다. 그래서 따로 설명을 쓰는것보다 링크를 추가하는것이 더 좋다고 생각된다.

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

 문자열 비교를 위해 사용될 2차원 배열을 만들어준다. 첫번째 행,열을 탐색할때를 위해서 1행,1열씩 추가로 구성해준다. 실제로 문자열 비교는 1행 1열부터 할것이다.(!)

0 0000000000

0 !

0

0

0

이런 모양이다.

let LCS = new Array(s.length+1);
for(let i=0; i<LCS.length; i++){
  LCS[i] = new Array(t.length+1).fill(0);
}

 

 이제 2차원 배열을 탐색하면서 문자열이 같은 알파벳인지 아닌지에 따라서 2차원 배열의 내용을 채워주면된다.

두 문자열의 알파벳이 같다면 해당 칸의 왼쪽위 칸에 있는 값에 1을 더해준다.(공통 부분 문자열의 길이가 1 늘어난다).

반대로 두 문자열의 알파벳이 다르다면 해당 칸의 값을 0 으로한다. 왜냐하면 공통 부분 문자열은 '연속된' 문자열 이기 때문이다.

for(let i=1; i<=s.length; i++){
  for(let j=1; j<=t.length; j++){
    if(s[i-1]===t[j-1])
      LCS[i][j] = LCS[i-1][j-1] + 1;
    else
      LCS[i][j] = 0;

    if(LCS[i][j] > answer)
      answer = LCS[i][j];
  }  
}

 

전체코드

const fs = require('fs');
const input = fs.readFileSync('공통 부분 문자열/input.txt').toString().trim().split('\n');

const s = input.shift().trim();
const t = input.shift().trim();
let answer = 0;

let LCS = new Array(s.length+1);
for(let i=0; i<LCS.length; i++){
  LCS[i] = new Array(t.length+1).fill(0);
}

for(let i=1; i<=s.length; i++){
  for(let j=1; j<=t.length; j++){
    if(s[i-1]===t[j-1])
      LCS[i][j] = LCS[i-1][j-1] + 1;
    else
      LCS[i][j] = 0;

    if(LCS[i][j] > answer)
      answer = LCS[i][j];
  }  
}

console.log(answer);

특이사항