[ NodeJS ] LCS(LongestCommonSubstring) 최장 공통 문자열 찾기

두개의 문자열을 비교하여 최장 공통 문자열 반환 알고리즘이다. 

구글링을 해보면 여러 소스들이 구현된 것을 확인할 수 있는데 대부분 2차 배열을 사용해서 구현이 되어 있다. 

하지만 글자수가 길어질 수록 메모리 부족으로 오류가 나타날 수 있기 때문에 위키백과(ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4) 하단에 요구공간 부족일 경우 2개의 배열만 가지고 해결하도록 추천을 해준다. 

그에 따른 소스 코드이다. 

 

function longestCommonSubstring(string1, string2) {

  const s1 = [...string1];
  const s2 = [...string2];

  var s1Length = s1.length;
  var s2Length = s2.length;

  var lastRow = Array(s2Length+1).fill(0);
  var currentRow = Array(s1Length+1).fill(0);

  let longestSubstringLength = 0;

  var rowChar = "";
  var colChar = "";

  for (let rowIndex = 1; rowIndex <= s2.length; rowIndex += 1) {
    rowChar = s1[rowIndex-1];

    for (let columnIndex = 1; columnIndex <= s1.length; columnIndex += 1) {
      colChar = s2[columnIndex-1];

      if (rowChar === colChar) {
        currentRow[columnIndex] = lastRow[columnIndex-1] + 1;
      } else {
        currentRow[columnIndex] = 0;
      }

      // Try to find the biggest length of all common substring lengths
      // and to memorize its last character position (indices)

      if (currentRow[columnIndex] > longestSubstringLength) {
        longestSubstringLength = currentRow[columnIndex];
      }
    }
    lastRow = currentRow.slice();
  }

  if (longestSubstringLength === 0) {
    // Longest common substring has not been found.
    return 0;
  }


  return longestSubstringLength;
}