#最长公共子串

export function longestCommonSubstring(str1: string, str2: string) {
  const m = str1.length
  const n = str2.length
  // 设 dp[i][j] 为 str1 [i, m), str2 [j, n) 的最长公共前缀长度
  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0))
  let max = 0
  let str1Index = 0

  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      dp[i][j] = str1[i] === str2[j] ? dp[i + 1][j + 1] + 1 : 0
      if (dp[i][j] > max) {
        max = dp[i][j]
        str1Index = i
      }
    }
  }

  return str1.slice(str1Index, str1Index + max)
}