描述

給定兩個只包含小寫字母的字符串，計算兩個字符串的最大公共子串的長度。
注：子串的定義指一個字符串刪掉其部分前綴和后綴（也可以不刪）后形成的字符串。
數(shù)據(jù)范圍：字符串長度：1≤s≤150
進階：時間復雜度：O(n^3) ，空間復雜度：O(n)

輸入描述：

輸入兩個只包含小寫字母的字符串

輸出描述：

輸出一個整數(shù)，代表最大公共子串的長度

示例1

輸入：
asdfas
werasdfaswer
輸出：
6

方法一：

使用match和substring實現(xiàn)
為啥把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之間的區(qū)別.png

substring()和substr之間的區(qū)別：

• substr()方法的兩個參數(shù)是start和length，而substring方法的參數(shù)是start和end
• 如果substr()的start索引為負數(shù)，它將循環(huán)到字符串的末尾，而 substring()會將其限制為0
• 在 substr()中，如果長度為負數(shù)，將被視為零；而在 substring()中，如果 end 小于 start ，則會交換這兩個索引。

此外，substr()被認為是ECMAScript中的遺留特性，因此如果可能的話最好避免使用它?。。?/p>

其他的解法

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

• 動態(tài)規(guī)劃算法-js實現(xiàn)
  空間復雜度還是o(n^2)，如何優(yōu)化到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);
    }
});