Max Palindrome/最大回文字符串

console.log("Hello World!");

/**
 *  求字符串所包含的最大回文数和至少要删除的字符个数
 *  字符串长度<1000
 *  如:google,回文数为goog,至少要删除2个字符
 */
 
 //求的是最长公共子串(应该求最长公共子序列)
 //全遍历,时间复杂度太高
  function getMaxPalindrome(str){
      var strReverse = str.split("").reverse().join("");
      var sLen = str.length, rLen = sLen;
      var palindromes = [];
      for(var i=0; i<sLen; i++){
          var ic = str[i];
          for(var j=0; j<rLen; j++){
              var jc = strReverse[j];
              if(ic == jc){
                  var k = 1;//palindrome len
                  while((i+k < sLen) && (j+k < rLen)
                        &&(str[i+k] == strReverse[j+k])){
                        k++;
                  }
                  if(k > 1){
                    palindromes.push(str.substr(i,k));
                  }
              }
          }
      }
      palindromes = palindromes.sort((a,b) => b.length-a.length);
      console.log(palindromes)
      let p = palindromes[0]||"";
      let start = p===""? -1:str.indexOf(p);
      return {
          str: str,
          palindrome: p,
          start: start,
          end: start+p.length
      };
  }
  

/**
 * 文本相似度匹配
 * Levenshtein distance算法
 */
function getMaxPalindrome2(src){
    let des = src.split("").reverse().join();
    let m = src.length;
    let n = des.length;
    
    var matrix = [];
    
    //初始化数组
    for(let i=0;i<=m;i++){
        matrix[i] = [];
        if(!i){
            for(let j=0;j<=n;j++){
                matrix[0][j] = j;
            }
        }else matrix[i][0] = i;
    }
    
    Array.prototype.min = function() {
    	return Math.min.apply({},this)
    }

    //计算两个字符是否一样，计算左上的值
    let temp;  
   
    for (let i = 1; i <= m; i++) {  
        for (let j = 1; j <= n; j++) {  
            temp = src[i-1]==des[j-1]?0:1; 
            //取三个值中最小的  
            matrix[i][j] = [matrix[i-1][j-1]+temp, matrix[i][j-1]+1, matrix[i-1][j]+1].min();  
        }  
    }  
    //console.log(matrix[m][n],Math.max(m,n),src.length,des.length)
    return Math.max(m,n) - matrix[m][n];  
}




// for test

console.time("自己遍历ET")
console.log(getMaxPalindrome("google"))
console.timeEnd("自己遍历ET")

console.log("-----------------------split line----------------------------------")

console.time("Levenshtein ET")
console.log("min distance: "+getMaxPalindrome2("google"));
console.timeEnd("Levenshtein ET")

console.log("-----------------------split line----------------------------------")

//文章链接：求的是最长公共子,最长公共子序列
console.log("文章链接：最长公共子串,最长公共子序列:\n https://www.jianshu.com/p/4b5d7deef7fe")