HJ75 公共子串计算

描述

给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
数据范围：字符串长度：1≤s≤150
进阶：时间复杂度：O(n^3) ，空间复杂度：O(n)

输入描述：

输入两个只包含小写字母的字符串

输出描述：

输出一个整数，代表最大公共子串的长度

示例1

输入：
asdfas
werasdfaswer
输出：
6

方法一：

使用match和substring实现
为啥把substring改成substr会有问题？？

const rl = require("readline").createInterface({ input: process.stdin });
let input_data = [];
rl.on("line", function (input) {
    input_data.push(input);
    if (input_data.length == 2) {
        let [s1, s2] = input_data;
        //确保s1是短字符串
        if (s1.length > s2.length) {
            let s3 = s1;
            s1 = s2;
            s2 = s3;
        }
        let len = s1.length;
        let max = 0;
        for(let i=0;i<len;i++){
            for(let j=i+1;j<=len;j++){
                if(s2.match(s1.substring(i,j))){
                    let temp = j-i
                    max=Math.max(max,temp)
                }else{
                    break
                }
            }
        }
        console.log(max);
    }
});

substring和substr之间的区别.png
参考：https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/String/substring

substring()和substr之间的区别：

• substr()方法的两个参数是start和length，而substring方法的参数是start和end
• 如果substr()的start索引为负数，它将循环到字符串的末尾，而 substring()会将其限制为0
• 在 substr()中，如果长度为负数，将被视为零；而在 substring()中，如果 end 小于 start ，则会交换这两个索引。

此外，substr()被认为是ECMAScript中的遗留特性，因此如果可能的话最好避免使用它！！！

其他的解法

https://blog.nowcoder.net/n/fd69366f4f6843b3b48632131483c87a?f=comment

• 动态规划算法-js实现
  空间复杂度还是o(n^2)，如何优化到o(n)??

const rl = require("readline").createInterface({ input: process.stdin });
let input_data = [];
rl.on("line", function (input) {
    input_data.push(input);
    if (input_data.length == 2) {
        let [s1, s2] = input_data;
        //确保s1是短字符串
        if (s1.length > s2.length) {
            let s3 = s1;
            s1 = s2;
            s2 = s3;
        }
        let len = s1.length;
        let len2 = s2.length
        let max = 0;
        let dp_arr=new Array(len)
        for(let i=0;i<len;i++){
            dp_arr[i]=new Array(len2)
            for(let j=0;j<len2;j++){
                if(s1[i]===s2[j]){
                    if(i===0||j===0){
                        dp_arr[i][j]=1
                    }else{
                        dp_arr[i][j]=1+dp_arr[i-1][j-1]
                    }
                    max=Math.max(dp_arr[i][j],max)
                }else{
                    dp_arr[i][j]=0
                }
            }
        }
        console.log(max);
    }
});