[백준][Node.js] 5582번 : 공통 부분 문자열

 

 

Algorithm

-  공통 부분 문자열 -

 

---

 

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

 

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

 

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

 

입출력 예시

 

문제 풀기

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let word1 = input[0];
let word2 = input[1];
let arr = [];
let max = 0;

for (let i = 0; i < word2.length; i++) {
	let value = Array(word1.length).fill(0);
	for (let j = 0; j < word1.length; j++) {
		if (word2[i] === word1[j]) {
			if (i - 1 < 0 || j - 1 < 0) value[j] = 1;
			else value[j] = arr[i - 1][j - 1] + 1;
			if (max < value[j]) max = value[j];
		}
	}
	arr.push(value);
}

console.log(max);