[JavaScript]最长公共子串

最长公共子串

• 描述
• 示例
• 代码
• • 暴力
  • 动态规划

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。

示例

输入：
"1AB2345CD","12345EF"
返回值：
"2345"

代码

暴力

/*** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/
function LCS( str1 ,  str2 ) {// write code herelet maxlength=0,index=0for(let i=0;i<str2.length;i++){for(let j=i+1;j<=str2.length;j++){if(str1.indexOf(str2.slice(i,j))!=-1){if(maxlength<j-i){maxlength=j-iindex=i}}}}if(!maxlength) return -1return str2.slice(index,maxlength+index)
}
module.exports = {LCS : LCS
};

动态规划

/*** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/
function LCS( str1 ,  str2 ) {// write code herelet dp=[]let maxi,maxjlet maxlen=0for(let i=0;i<str1.length+1;i++){dp[i]=[]for(let j=0;j<str2.length+1;j++){dp[i].push(0)}}for(let i=1;i<str1.length+1;i++){for(let j=1;j<str2.length+1;j++){if(str1[i-1]!=str2[j-1]){dp[i][j]=0}else{dp[i][j]=dp[i-1][j-1]+1;if(dp[i][j]>maxlen){maxlen=dp[i][j]maxi=imaxj=j}}}}return str2.slice(maxj-maxlen,maxj)}
module.exports = {LCS : LCS
};