题解 | #公共子串计算#暴力求解与动态规划

暴力法即使用双指针，不断截取较短串长度，记录最大值

使用动态规划对暴力法进行优化，使用dp记录上一步操作值，减小计算量

let s1=readline();
let s2=readline();
let maxn=0,dp=[]
// if(s1.length>s2.length){//令s1为较短
//     let a=s2;
//     s2=s1;
//     s1=a;
// }
// for(let i=0;i<s1.length;i++){//暴力法
//     for(let j=i;j<s1.length;j++){
//         if(s2.indexOf(s1.slice(i,j+1)) != -1 && j+1-i>maxn ){
//             maxn=j+1-i;
//         }
//     }
// }

for(let i = 0;i<=s1.length;i++){//动态规划，生成数组
    dp[i] = [];
    for(let j = 0;j<=s2.length;j++) dp[i][j] = 0;
}
 for(let i = 0;i<s1.length;i++){
    for(let j = 0;j<s2.length;j++) {
        if(s1[i] == s2[j]) dp[i+1][j+1] = dp[i][j] + 1;
        else  dp[i+1][j+1] = 0;
    }
}
for(let k of dp) maxn = Math.max(...k)>maxn? Math.max(...k):maxn
print(maxn)