算法题之字符串 | GeniusFunny的个人博客

算法题之字符串～～～

最长公共子序列

题目

找出两个字符串中最长公共子序列（非最长连续子序列）

解决方案

• 动态规划：写出状态方程

  • 当i=0，j=0时，c[i,j] = 0
  • 当a[i] = b[j]时，c[i,j] = c[i-1, j-1] + 1
  • 当a[i] 不等于 b[j]时，c[i,j] = max(c[i,j-1], c[i-1, j])

  function LCS(strA, strB) {
    let dp = {};
    let lenA = strA.length;
    let lenB = strB.length;
  
    dp['-1,-1'] = 0
    for(let i = 0; i < lenA; i++) {
      dp[`${i},-1`] = 0;
    }
    for(let i = 0; i < lenB; i++) {
      dp[`-1,${i}`] = 0;
    }
  
    for(let i = 0; i < lenA; i++) {
      for(let j = 0; j < lenB; j++) {
        if(strA[i] === strB[j]) {
          dp[`${i},${j}`] = dp[`${i-1},${j-1}`] + 1;
        } else {
          dp[`${i},${j}`] = Math.max(dp[`${i},${j-1}`], dp[`${i-1},${j}`]);
        }
      }
    }
    return dp[`${lenA-1},${lenB-1}`];
  }

KMP

题目

判断字符串A是否是字符串B的子串

解决方案

• 指针a指向字符串A，指针b指向字符串b，next数组为部分匹配表（字符串A的前缀后缀最长公共序列长度）
• 若a尚未匹配到元素
  • a指向的内容若不等于b指向的内容，则b++
  • 若相等，二者同时++
• 若a已有匹配元素
  • 若a指向的内容若不等于b指向的内容
    • b += （a - next[a-1])
    • a = 0
  • 若相等，二者同时++

// 计算部分匹配表，即next数组
function makeNext(str) {
  const next = []
  const len = str.length;
  next[0] = 0;
  for(let i = 1, k = 0; i < len; i++) {
    while(k && str[i] !== str[k]) k = next[k-1] // 核心
    if(str[k] === str[i]) k++;
    next[i] = k;
  }
  return next;
}
// 匹配
function kmp(strA, strB) {
  const next = makeNext(strA);
  const lenA = strA.length;
  const lenB = strB.length;
  let i = j = 0;
  while(i < lenA && j < lenB) {
    if (strA[i] === strB[j]) {
      i++;
      j++;
    } else{
      if(i > 0) {
        j += (i - next[i-1]); // j往后移动已匹配字符数-部分匹配表对应的数目
        i = 0;
      } else {
        j++;
      }
    }
    if (i === lenA) {
      console.log('匹配成功', strA, strB.slice(j-lenB, j));
      return true;
    }
  }
  console.log('匹配失败')
  return false;