负责的项目中的富文本编辑器要新增搜索高亮的功能，在字符串匹配搜索中比较有名的就是 KMP 算法，下面来简单介绍下 KMP 以及如何在项目中应用。

在常规的字符串匹配中，比较简单的方案就是一个字符一个字符地去对比。

这里第三个字符 C 与 D 不相等，匹配失败

那么将原字符串指针回归到起始位置后一位，匹配字符串指针回归到起始位置继续匹配。这样的做法比较暴力，在 KMP 中有优化的方案。比如在匹配字符串中，D 字符串匹配失败，但前面的 A 与 B 并不相等，能确保 D 前面的字符串不重复，所以无需将原字符串指针回归到起始位置后一位。

那如果匹配字符串有重复字符呢？

如上图，存在 AB 字符串相同。根据 KMP 中的方法，我们可以将匹配字符串的指针回到 AB 字符串长度 2 的位置

AB 字符串就是在匹配字符串 E 点匹配失败的前面字符串 ABCAB 中的最长公共前后缀字符串。

比如前缀有 A，AB，ABC，ABCA，后缀有 B，AB，CAB，BCAB，公共的前后缀就是 AB。

也就是什么时候匹配失败了，我就去找前面的字符的最长公共前后缀字符串的长度，指针回到该位置就行了。

这里的最长公共前后缀字符串只跟匹配字符串有关，所以可以列一张表，展示对应关系

匹配失败位置	字符串	公共的前后缀字符串	公共的前后缀字符串长度
A	''	''	-1
B	A	''	0
C	AB	''	0
A	ABC	''	0
B	ABCA	A	1
E	ABCAB	AB	2

得到一个除当前字符外的最长公共前后缀的长度数组，称为 next 列表 [-1, 0, 0, 0, 1, 2]。

如果第一个 A 字符就匹配失败，由于前面没有字符，且原字符串的指针也得后移，这里就定义为 -1。

我们可以通过 2 个指针，遍历匹配字符串来获得 next 列表。首先将列表固定为 [-1]，表示在第一个 A 字符就匹配失败。

当第二个 B 字符串匹配失败时，前面的字符串只有 A，表示没有公共前后缀，长度设置为 0，此时记做 [-1, 0]

蓝色指针往后移，当第三个 C 字符匹配失败时，前面字符串 AB，两个指针位置的字符 A 与 B 并不相等，所以也没有公共前后缀，长度设置为 0，此时记做 [-1, 0, 0]

蓝色指针往后移，当第四个 A 字符匹配失败时，前面字符串 ABC，两个指针位置的字符 A 与 C 并不相等，所以也没有公共前后缀，长度设置为 0，此时记做 [-1, 0, 0, 0]

蓝色继续后移，这时候两个指针位置的字符相等了，长度为 1，记做 [-1, 0, 0, 0, 1]。 这时可能会有疑问，有没有可能还有更长的情况呢，假设 AX = XA，那么只有可能是 AAAA，那之前的公共前后缀长度就不可能是 0 了。

遇到相等情况下，那么红色指针也开始后移了，来判断第二个字符是否相等。这时也是相等的，得再上一个基础上长度 +1，记做 [-1, 0, 0, 0, 1, 2]

两个指针再往后移，不相等，则回归到 0 位置，在与 E 相比，不相等则没有公共前后缀，记做 [-1, 0, 0, 0, 1, 2, 0]

转换成代码

function nextList(pattern) {
    let i = 0;
    let j = -1;
    const next = [];
    next[0] = -1;
    while (i < pattern.length) {
        if (j === -1 || pattern[i] === pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

后面就比较简单了，根据 KMP 的策略，两个指针位置字符对比，匹配失败，匹配的字符串的指针位置回到 next 对应的位置，继续对比。如果是第一个字符就匹配失败，那么原字符串的指针也往后移。

最后当匹配字符串的指针走完后，返回两指针位置差就是字符串匹配成功的起始位置。

function kmp(str, pattern){
  const next = nextList(pattern);
  let i = 0;
  let j = 0;
  while (i < str.length && j < pattern.length) {
    if (str[i] === pattern[j] || j === -1) {
      i++;
      j++;
    } else {
      j = next[j];
    }
  }
  if (j === pattern.length) {
    return i - j;
  } else {
    return -1;
  }
}

回到项目中来，我们具体的需求是在富文本编辑器中添加搜索功能，搜到所以匹配的词然后标记高亮，并且还能上下切换

与原版的 KMP 算法不同，在实际的项目中并不是一个纯字符串匹配搜索。

比如在富文本编辑器中的内容格式就分为词和分词

const words = [
  {
    chs: [
      {
        ch: '这'
      },
      {
        ch: '是'
      }
    ]
  },
  {
    chs: [
      {
        ch: '一段'
      }
    ]
  },
  {
    chs: [
      {
        ch: '话'
      }
    ]
  }
]

并且查找的还是所有词，并不需要返回结果位置，而是高亮标记

const words = [
  {
    chs: [
      {
        ch: '这',
        highlight: true, // 高亮
      },
      {
        ch: '是'
      }
    ]
  },
]

所以对原来的 KMP 代码进行改造，首页因为不是纯字符串，所以原代码中 str[i] 和 i++ 就无法使用，我们可以创建一个搜索内容类，提供 text() 和 next() 方法来代替当前字符和指针后移的功能

class SearchContent {
  constructor(words) {
    this.words = words;
    this.wIndex = 0; // 词索引
    this.cIndex = 0; // 分词索引
    this.i = 0; // 字符指针
    this.isEnd = false; // 指针是否到底
  }
  
  text() {
    return this.words[this.wIndex].chs[this.cIndex].ch[this.i];
  }
  
  next() {
    const word = this.words[this.wIndex];
    const text = word.chs[this.cIndex];
    this.i++;
    if (this.i >= text.ch.length) {
      this.i = 0;
      this.cIndex++;
    }
    if (this.cIndex >= word.chs.length) {
      this.cIndex = 0;
      this.wIndex++;
    }
    if (this.wIndex >= this.words.length) {
      this.isEnd = true;
    }
  }
}

KMP 的代码就改成

function kmp(words, pattern){
  const next = nextList(pattern);
  const content = new SearchContent(words);
  // let i = 0;
  let j = 0;
  while (!content.isEnd && j < pattern.length) {
    if (content.text() === pattern[j] || j === -1) {
      // i++;
      content.next();
      j++;
    } else {
      j = next[j];
    }
  }
  if (j === pattern.length) {
    return i - j;
  } else {
    return -1;
  }
}

接下来我们并不是只搜索一个词，所以不需要 j < pattern.length 这个条件，指针到底，重置继续搜索

function kmp(words, pattern){
  const next = nextList(pattern);
  const content = new SearchContent(words);
  // let i = 0;
  let j = 0;
  while (!content.isEnd) {
    if (content.text() === pattern[j] || j === -1) {
      // i++;
      content.next();
      j++;
      if (j === pattern.length) { // 重置指针位置，继续搜索
        j = 0;
      }
    } else {
      j = next[j];
    }
  }
  // if (j === pattern.length) {
  //   return i - j;
  // } else {
  //   return -1;
  // }
}

最后添加字符匹配成功的标记位置功能，搜索到词保存所有的位置功能，匹配失败后的清空位置功能。

class SearchContent {
  constructor(words) {
    this.words = words;
    this.wIndex = 0; // 词索引
    this.cIndex = 0; // 分词索引
    this.i = 0; // 字符指针
    this.isEnd = false; // 指针是否到底
    this.textList = []; // 储存每个字符的位置
    this.result = []; // 最终匹配结果
    this.index = 1; // 搜索结果索引，用来标记当前高亮状态，上下切换功能
  }
  
  // 标记位置
  mark() {
    // 记录 词索引、分词索引、分词起始位置、分词结尾位置、搜索结果索引
    if (this.textList.length > 0) {
      const last = this.textList[this.textList.length - 1];
      const [wIndex, cIndex] = last;
      if (wIndex === this.wIndex && cIndex === this.cIndex) {
        last[3] = this.i;
      } else {
        this.textList.push([this.wIndex, this.cIndex, this.i, this.i, this.index]);
      }
    } else {
      this.textList.push([this.wIndex, this.cIndex, this.i, this.i, this.index]);
    }
  }
  
  // 搜索到词后保存位置
  save() {
    this.result.push(this.textList);
    this.index++;
    this.clear();
  }
 
  // 匹配失败后清空位置
  clear() {
    this.textList = [];
  }
}

KMP 的代码就改成

function kmp(words, pattern){
  const next = nextList(pattern);
  const content = new SearchContent(words);
  // let i = 0;
  let j = 0;
  while (!content.isEnd && j < pattern.length) {
    if (content.text() === pattern[j]) {
      // i++;
      content.mark(); // 标记位置
      content.next();
      j++;
      if (j === pattern.length) {
        j = 0;
        content.save(); // 搜索到词后保存所有位置
      }
    } else if (j === -1) {
      content.clear(); // 匹配失败清空
      content.next();
      j++;
    } else {
      content.clear();
      j = next[j];
    }
  }
  console.log(content.result)
}

打印结果

上图表示这一段找到了 3 个词，位置在 第 19 词，第 0 分词中 1-2 索引位置。20 则表示总搜索到的第 20 个词。