字符串处理算法总结：KMP算法和Tier字典

2024-12-03 来源：个人技术集锦

KMP算法

使用场景：已知一个字符串S和一个模式串P，查找P在S中的位置？
字符串S： i指向当前字符
字符串P： j指向当前字符

暴力搜索

思路：逐个字符匹配即可。
问题：对于已知的情况会出现反复对比的操作，效率降低

KMP

思路：对模式串P进行分析，使得当S的一部分和P不匹配时，可以快速略过已知的不匹配的字符
做法：从模式串P中得到next数组，用next数组来表示如果当前字符(S[i] != P[j])不匹配，下一个P对应的j的位置, 而i只管一路向后i++

求next数组

理解方式：next其实也可以表示当前字符j之前的0 ~（j-1）位置的字符中，相同的前缀后缀的字符串的数量（长度）。这个数量其实就等于j下一个位置，因为P的索引以0开始。

（这样就说明如果此时j不匹配，但是我前面有一部分是和前缀相同的，就可以不重复匹配了！）

  private static void getNext(int[] next, String P){
        int len = P.length();
        int k = -1;
        int j = 0;
        next[0] = -1;//初始值，对应kj的初始值
        while(j < len-1){
            //k==-1即到头了，没有匹配的了，只好“重头再来”
            if(k == -1 || P.charAt(j) == P.charAt(k)){
                next[j+1] = k + 1;//得到next[j+1]
                k++;
                j++;
            }else{
                k = next[k];
            }
        }
  }

时间复杂度为O(lenP)

KMP匹配

匹配到的时候，i++；匹配不到的时候，j = next[j]找到下一个位置即可。

  private static boolean KMP(String S, String P, int[] next){
      int plen = P.length();
      int slen = S.length();
      int i = 0;//S上的指针
      int j = 0;//P上的指针

      while(i < slen && j < plen){
          //j =- 1说明没有相似的，P模式串从头匹配
          if(j == -1 || S.charAt(i) == P.charAt(j)){
              i++;j++;
          }else{
              //当前不相等时，下一个要匹配的模式串P的位置
              j = next[j];
          }
      }
      // return i-j
      if(j == plen){
           System.out.println(i-j);
           return true;
        }

      return false;
  }

总体时间复杂度O（lenS+lenP），使用空间换时间的思路，next数组的空间为O（lenP）

String的indexOf()

同样是搜索字符串在字符串中的位置，这里提一下indexOf()的实现原理。基本上是稍微优化了的暴力搜索：

 static int indexOf(String source, String target, int fromIndex) {
        final int sourceLength = source.length();
        final int targetLength = target.length();
        if (fromIndex >= sourceLength) {
            return (targetLength == 0 ? sourceLength : -1);
        }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        if (targetLength == 0) {
            return fromIndex;
        }

        char first = target.charAt(0);
        // 计算出最多比较的次数
        int max = (sourceLength - targetLength);

        for (int i = fromIndex; i <= max; i++) {
            // 寻找在source中出现和target第一个字符相等的位置
            if (source.charAt(i)!= first) {
                while (++i <= max && source.charAt(i) != first);
            }

            if (i <= max) {
                // 找到第一个相等的字符后，从下一个字符开始再比较（下次比较开始的位置）
                int j = i + 1;
                // 除target第一个字符，剩下字符再比较结束的位置
                // 可以理解为：j+(targetLength-1)， 即开始的位置+ target剩下要比较字符的长度
                int end = j + targetLength - 1;
                /* j < end 说明还没有比较完
                 * j < end && source.charAt(j) == target.charAt(k) 是真说明在还没比较完的情况下比较的字符相等，
                 *  那么继续循环，直到条件为false
                 */
                for (int k = 1; j < end && source.charAt(j) == target.charAt(k); j++, k++);

                // 上面循环结束时 j刚好等于结束比较的位置，那么就返回上面找到的target第一个字符相等的位置
                if (j == end) {
                    return i;
                }
            }
        }
        return -1;
    }

KMP适合重复串多的搜索，而且字符串不长的情况下，耗费的时间并不少。
在Leetcode中用KMP会比用indexOf函数慢很多。

Trie字典

使用场景：用于存储和搜索字符串
数据结构：树结构，一个节点存储1个字符，如果只考虑小写，每个节点可能由26个子节点。

相比平衡树和哈希表的优点：

可以找到具有同一前缀的全部字符串
可以按照字典序，枚举字符串集合
Trie搜索的时间复杂度为O(m)，m为字符串长度，而平衡树为O(mlogn)，n为字符串数量

节点结构

Trie为一个有根的树，节点有2个字段：

boolean变量，表示该字符是不是单词的最后一个字符
Map数组，存储key-value即【字符——子节点】值，可以看到字符其实是存储在父节点的Map数组里面（也可以用定长的26长度的数组直接存储子节点，使用Hash会比直接使用数组慢很多）

操作

相关的操作有：插入单词，搜索单词，搜索前缀等
删除操作相对复杂一点：
1. 如果删除的单词是另外一个单词的前缀
2. 如果删除的单词没有任何分支
3. 如果删除的单词和别的单词有共同的前缀

实操练习

Leetcode 208, 211 和 677问题

参考文献：

以下都是很好的文章：

非常透彻细致的KMP算法讲解：

显示全文

全部栏目