// 1) составить матрицу из 0
// 2) если буква на i месте  не совпадают, то 0
// 3) если совпадают, то берется значение из предыдущей ячейки и увеличивается на 1
// 4) обновляется максимальная подстрока


const createMatrix = (row, col) => {
  const arr = Array(row).fill(Array(col).fill(0));
  return JSON.parse(JSON.stringify(arr));
}

const maxCommonSubstring = (str1, str2) => {
  const matrix = createMatrix(str1.length, str2.length);

  let maxSize = 0;
  let endIndex = 0;

  for (let i = 0; i < str1.length; i++) {
    for (let j = 0; j < str2.length; j++) {
      if (str1[i] !== str2[j]) {
        continue
      }

      matrix[i][j] = (i && j) > 0 ? matrix[i - 1][j - 1] + 1 : 1;

      if (matrix[i][j] >= maxSize) {
        maxSize = matrix[i][j];
        endIndex = j + 1;
      }
    }
  }

  return str1.slice(endIndex - maxSize, endIndex);
}


maxCommonSubstring('fish', 'hish');  // 'ish'
maxCommonSubstring('fish', 'fista'); // 'fis'
maxCommonSubstring('fish', 'fista'); // 'is'


const maxCommonSubsequence = (str1, str2) => {
  const matrix = createMatrix(str1.length, str2.length);

  for (let i = 0; i < str1.length; i++) {
    for (let j = 0; j < str2.length; j++) {
      if (str1[i] === str2[j]) {
        matrix[i][j] = (i && j) > 0 ? matrix[i - 1][j - 1] + 1 : 1;
      } else {
        const left = i > 0 ? matrix[i - 1][j] : 0;
        const up =  j > 0 ? matrix[i][j - 1] : 0

        matrix[i][j] = Math.max(left, up);
      }
    }
  }


  return matrix[str1.length - 1][str2.length - 1]
}

maxCommonSubsequence('fort', 'fosh'); // 2
maxCommonSubsequence('fish', 'fosh'); // 3