基本概念

  • 子串：串中任意个连续字符组成的子序列称为该串的子串。
  • 主串：包含子串的串。

  • 子串的位置：子串的第一个字符在主串中的序号。

    字典排序

    字符串比较大小通过字典排序，本质上是比较 ascll 码的大小。

    串和线性表

    串和线性表非常像，区别在于：

  • 线性表关注与单个元素的操作，增删改查

  • 串更专注于子串的操作，查找子串，替换子串。

    BF算法

    在主串中找到子串的定位操作叫做模式匹配。朴素解法即对主串做大循环，对每个字符做子串长度的小循环。 ```jsx function findIndex(mStr, sStr) { const mLen = mStr.length;

    1. const sLen = sStr.length;

    if(mLen < sLen) {

    1.   return -1;

    }

    for (let i=0; i<(mLen-sLen+1); i++) {

    1.   for (let j=0; j<sLen; j++) {
    2.       if (mStr[i+j] !== sStr[j]) {
    3.           break;
    4.       }
    5.       if(j === sLen - 1) {
    6.           return i;
    7.       }
    8.   }

    } return -1;

  1. 时间复杂度：最坏情况是 O((n-m+1)*m) 对大循环进行到底
  2. <a name="XzU5A"></a>
  3. ## KMP算法
  4. **约定主串 `txt` ，子串 `pat`**
  6. KMP 算法的不同之处在于，它会花费空间来记录一些信息，让 BF 算法中无意义的比较少一点。KMP 算法永不回退 txt 的指针 i，不走回头路（不会重复扫描 txt），而是借助 dp 数组中储存的信息把 pat 移到正确的位置继续匹配。
  8. 根据前缀和后缀共有元素的个数，构成部分匹配表，计算出 pat 指针回溯位数 ，移动位数 = 已匹配的字符数 - 对应的部分匹配值。
  9. ```jsx
  10. var strStr = function(haystack, needle) {
  11.     var m = haystack.length, n = needle.length;
  12.     if(!n) return 0;
  13.     var next = kmpProcess(needle);
  14.     for(var i = 0, j = 0; i < m;) {
  15.         if(haystack[i] == needle[j]) { // 字符匹配，i和j都向前一步
  16.             i++, j++;
  17.         }
  18.         if(j == n) return i - j; // needle完全匹配上，返回匹配位置
  19.         if(haystack[i] != needle[j]) { // 字符不匹配
  20.             if(j > 0) {
  21.                 j = next[j-1]; // 重置j
  22.             } else {
  23.                 i++;
  24.             }
  26.         }
  28.     }
  29.     return -1;
  30. };
  32. var kmpProcess = function(needle) {
  33.     var y = 0;
  34.     var x = 1;
  35.     var next = new Array(needle.length).fill(0);
  36.     while (x < needle.length) {
  37.         if (needle[x] == needle[y]) {
  38.             y++;
  39.             next[x] = y;
  40.             x++;
  41.         } else if (y > 0) {
  42.             y = next[y - 1];
  43.         } else {
  44.             next[x] = 0;
  45.             x++;
  46.         }
  47.     }
  48.     return next;
  49. }
  51. console.log(strStr('abcabcabya', 'abcaby')); // 3

假设x是遍历needle的索引，y是neddle数组从0开始的索引，也是j将要重置的位置(即存入next数组的值)。因为needle的第一个字符没有前后缀，所以next[0]永远是0，所以x从1开始。计算next的过程如下：

  1. needle[x] != neddle[y]，由于y=0，所以next[x]=0，并且x向前一步，如下图：串 - 图1

2.needle[x] != neddle[y]，由于y=0，所以next[x]=0，并且x向前一步，如下图：
串 - 图2

  1. needle[x] == neddle[y]，如下图：
    串 - 图3此时y要先前进一步，next[x]=前进后的y(此时为1)，并且x也向前一步，此时next[x]即next[3]=1如下图：串 - 图4
  2. needle[x] == neddle[y]，如下图：
    串 - 图5此时y要先前进一步，next[x]=前进后的y(此时为2)，并且x也向前一步，此时next[x]即next[4]=2如下图：

串 - 图6
5.needle[x] != neddle[y]，由于y != 0，说明之前有匹配上的字符串，此时需要移动y至next[y-1]，即y=0，再去比较needle[x] 与 neddle[y]，注意，y !=0 或者needle[x] != neddle[y]时，x不能前进，要保持在原地，如下图：
串 - 图7根据needle[x] 与neddle[y]相等和不相等的情况，反复上述步骤，直到needle遍历完为止。此时needle[x] !=neddle[y]且y=0，所以next[x]=0。 这时next数组也被填充完了，如下图。串 - 图8
最后得到next数组为：[0, 0, 0, 1, 2, 0]