[백준/G5] 공통 부분 문자열

https://www.acmicpc.net/problem/5582

시간복잡도

O(N**2)

풀이

LCS 알고리즘 원리를 사용

문제에서 제시한 조건상으로 연속된 공통문자열이므로 문자열이 끊이지 않는 조건이다.

즉, 기본적인 LCS 알고리즘보다 간단히 풀이하여 비교한 값이 같을 경우 그전까지 같았던 이력(dp)+1로 구하면 된다

// 두 문자열에 포함된 가장 긴 공통 부분 문자열
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./5582.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const s1 = input[0];
const s2 = input[1];

const dp = Array(s1.length+1)
  .fill()
  .map(() => Array(s2.length+1).fill(0));

let maxVal = 0;
for (let i = 1; i <= s1.length; i++) {
  for (let j = 1; j <= s2.length; j++) {
    if (s1[i - 1] === s2[j - 1]) {
      dp[i][j] = dp[i - 1][j - 1] + 1;
			// 최대값 업데이트
      maxVal = Math.max(maxVal, dp[i][j]);
    }
  }
}
console.log(maxVal)

158092kb 704ms