动态规划

对于最长公共字串类似问题都可以使用动态规划来做。思路可以由递归->记忆化搜索 -> 动态规划发展而来

动态规划适用于最优子结构的问题，即该问题可以分解为子问题来解决。

同时也适用于重叠子问题：比起递归算法，动态规划会记录重复的子问题的结果，从而减小时间复杂度（递归时可以使用记忆化搜索，即使用数组，cache等结构记录已经递归到的结果，下次递归到时就不用计算了，这样和动态规划的时空复杂度相同O(m*n）

该问题是求最长公共子串，并且要求存在多个相同长度子串时返回较短字符串的第一个子串，所以首先预处理得到两个字符串shorter, longer

使用dp时通常要先明确dp数组表示什么，然后明确动态转移方程和边界情况

所以用dp[i][j] 表示的以i,j结尾的最长公共子串的长度。

1. 不同于最长公共子序列，子串必须是连续的，所以当 short[i] != short[j] 时dp数组设置为0即可。
2. 如果当short[i] = short[j]时，我们需要用到以i-1, j- 1结尾的的最长公共子串长度（我们已经存在了dp[i - 1][j - 1]），让其加1即可。 可以画表来帮助理解。

可以添加一行一列，便于初始化

我们要输出的是最长的子串，dp数组记录的是以i,j结尾的最长公共子串的长度。所以需要记录0-i , 0-j 最长公共子串的长度，以及该子串结尾在shorter字符串的下标以便输出

空间复杂度为O(m*n)

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

function findLongestCommanSubstring(str1, str2) {

    let shorter = str1.length < str2.length ? str1 : str2
    let longer =  str1.length < str2.length ? str2 : str1
    
    let dp = new Array(shorter.length + 1).fill(0).map(()=>new Array(longer.length+1).fill(0))
    let maxLen = 0
    let maxIdx = -1

    for(let i = 1; i <= shorter.length; i++) {
        for(let j = 1; j <= longer.length; j++) {
            if(shorter[i - 1] === longer[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
                if(dp[i][j] > maxLen) {
                    maxIdx = i
                    maxLen = dp[i][j]
                }
            } else {
                dp[i][j] = 0
            }
        }
    }
    if(maxLen === 0) return''
    return shorter.substring(maxIdx - maxLen, maxIdx)
}


void async function () {
    // Write your code here
    while(line = await readline()){
        let str1 = line
        let str2 = await readline()

        console.log(findLongestCommanSubstring(str1, str2))
    }
}()

滚动数组优化

由转移方程可知，dp[i][j]仅仅依赖于dp[i-1][j-1] ，在表中表现为它左上角的值，那么我们可以只用dp数组的当前行和上一行进行转移，即两个一维数组cur, pre。又因为若存在两个相同长度的最长子串，应返回在shorter中最先出现的那个，所以我们需要在外层遍历较短数组。从而将空间复杂度控制在O(max(m,n))

function findLongestCommanSubstring(str1, str2) {

    let shorter = str1.length < str2.length ? str1 : str2
    let longer =  str1.length < str2.length ? str2 : str1
    
    let cur = new Array(longer.length + 1).fill(0)
    let pre = new Array(longer.length + 1).fill(0)
    let maxLen = 0
    let maxIdx = -1
    for(let i = 1; i <= shorter.length; i++) {
        for(let j = 1; j <= longer.length; j++) {
            if(shorter[i - 1] === longer[j - 1]) {
                cur[j] = pre[j - 1] + 1
                if(cur[j] > maxLen) {
                    maxLen = cur[j]
                    maxIdx = i - 1
                }
            } else {
                cur[j] = 0
            }
        }
        [pre,cur] = [cur, pre]
    }
    if(maxLen === 0) return''
    return shorter.substring(maxIdx - maxLen+1, maxIdx +1)
}