题解 | #66.最长公共子串#

这里的dp含义和上一次不一样了，最长公共子序列的dp[i][j]表示str1的i位置和st2的j位置截止的最大长度，

而最长公共字串的dp[i][j]表示str1的i位置和str2的j位置作为最后一个元素所构成的最长公共字串，也就是str1的第i个位置必须作为公共子串的最后一个元素，在dp的过程中用index记录最大字串长度的最后一个元素下标

/*
  定义dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串。
  如果要求dp[i][j]，也就是str1的第i个字符和str2的第j个字符为最后一个元素所构成的最长公共子串
*/
function LCS( str1 ,  str2 ) {
  let maxLength = 0;//最大字串长度
  let index;//ii记录max最大时候的坐标，用于确定子串
  let dp = [];
  for(let i=0; i<str1.length; i++)
    dp.push([]);
  
  for(let i=0; i<str2.length; i++)
    dp[0][i] = (str1[0]==str2[i]) ? 1:0;
  
  for(let i=0; i<str1.length;i++)
    dp[i][0] = (str2[0]==str1[i]) ? 1:0;
  
  for(let i=1; i<str1.length; i++){
    for(let j=1; j<str2.length; j++){
      if(str1[i]==str2[j]){
        dp[i][j] = dp[i-1][j-1] + 1;
        if(maxLength < dp[i][j]){
          maxLength = dp[i][j];
          index = i;
        }
      }else{
        dp[i][j] =0;
      }
    }
  }
  
  return str1.substring(index-maxLength+1,index+1)
}