KMP算法

KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

KMP处理重复问题

在处理字符串匹配的问题时，例如 aabaabaafa 字符串匹配 aabaaf 字符串，使用暴力解法，即每次遍历文本串 aabaabaafa 都往模式串 aabaaf 中重新匹配，此时时间复杂为 O(m * n)，使用KMP算法的核心思想可以避免从头再去比较，大幅降低寻找字串的时间复杂度。

KMP前提

前缀集合和后缀集合

什么是前缀集合？什么是后缀集合？

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。我自己理解的前缀集合就是除开最后一个元素后前面元素集合（有多个）。

举个栗子：上边的模式串 aabaaf 的第6个数的前缀集合有 a,aa,aab,aaba,aabaa ，这5个就是该文本串的前缀集合（除开最后一个元素）。

那么后缀集合也就不言而喻了，和前缀集合相反。

模式串 aabaaf 的第6个数的后缀集合为 f,af,aaf,baaf,abaaf 这5个就是后缀集合（除开第一个元素）。

什么是前缀表？

在KMP中回退到哪个位置就是由next数组决定的！！！而next的本质就是一个前缀表！！！

此处演示第6个字符匹配的情况，此时回退的位置就时next数组决定。

KMP算法 - 图1

在KMP中前缀表是如何记录的呢？

前缀表的任务为：当前任务匹配失败后，找到之前已经匹配的位置再重新匹配，这页意味着再某个字符失效时，前缀表会告诉你下一步匹配时模式串应该跳到哪个位置。

那么什么是前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

最长公共前后缀

因为前缀表要求的就是相同前后缀的长度。

而最长公共前后缀里面的“公共”，更像是说前缀和后缀公共的长度。这其实并不是前缀表所需要的。

所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等…..。

为什么一定要用前缀表?

这就是前缀表，那为啥就能告诉我们 上次匹配的位置，并跳过去呢？

刚刚在f的时候不匹配：

KMP算法 - 图2

然后就找到了下标2，指向b，继续匹配：如图：

KMP算法 - 图3

下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了。也就是不匹配时，寻找此字符的最大相等前后缀，此时可以找到文本串匹配过的aa在模式串串前面有对应aa，所以直接从aa开始匹配，就不用跳到第一个元素开始匹配。(此时next数组就存放应该跳转到哪个位置！)

如何计算next数组

next数组就是前缀表，但是有不同的表示方法。

构造next数组其实就是计算模式串s，前缀表的过程。

  1. 初始化
  2. 处理前后缀不相同的情况
  3. 处理前后缀相同的情况

前缀表减一的模拟：

KMP算法 - 图4

如果生成的数组是减一的话，直接使用next对应的数组值回退。

  1. /**
  2.  * 前缀表减一的实现
  3.  *
  4.  * @param next
  5.  * @param s
  6.  */
  7. public void getNext(int[] next, String s) {
  8.     // j从0开始，此时next数组初始化
  9.     int j = -1;
  10.     next[0] = j;
  11.     for (int i = 1; i < s.length(); i++) {
  12.         // j要保证大于等于0，因为下面有取j作为数组下标的操作
  13.         while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
  14.             // 查找前一位对应的回退位置
  15.             j = next[j];
  16.         }
  18.         // 相等即向后移动
  19.         if (s.charAt(i) == s.charAt(j + 1)) {
  20.             j++;
  21.         }
  23.         next[i] = j;    // 将j(前缀的长度)赋值给next[i]
  24.     }
  25. }

如果next如果不减一的话，回退就需要使用前一个数对应的next数组值来回退。

  1. /**
  2.   * 生成next数组，（不减一的代码实现）
  3.   *
  4.   * @param next
  5.   * @param s
  6.   */
  7. public void getNext(int[] next, String s) {
  8.     // j从0开始，此时next数组初始化
  9.     int j = 0;
  10.     next[0] = 0;
  11.     for (int i = 1; i < s.length(); i++) {
  12.         // j要保证大于0
  13.         while (j > 0 && s.charAt(i) != s.charAt(j)) {
  14.             // 查找前一位对应的回退位置
  15.             j = next[j - 1];
  16.         }
  18.         // 相等即向后移动
  19.         if (s.charAt(i) == s.charAt(j)) {
  20.             j++;
  21.         }
  23.         next[i] = j;    // 将j(前缀的长度)赋值给next[i]
  24.     }
  25. }

时间复杂度

计算一个next数组时间复杂度O(m)，总的时间复杂度即为O(m + n)。

例题

通过使用next数组来解题。

实现 strStr()

题目描述

力扣链接🔗

KMP算法 - 图5

思路

使用next数组进行匹配，不匹配到不相同时，根据next回退。

代码

  • 前缀表不减一 ```java public int strStr(String haystack, String needle) { // 先判断模式串是否为0 if (needle.length() == 0) {

    1.  return 0;

    }

    int[] next = new int[needle.length()]; getNext(next, needle); // 获取模式串的next数组

    int j = 0; // next数组中初始位置为0 for (int i = 0; i < haystack.length(); i++) {

    1.  while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
    2.      j = next[j - 1];
    3.  }
    5.  if (haystack.charAt(i) == needle.charAt(j)) {
    6.      j++;
    7.  }
    9.  if (j == needle.length()) {
    10.      return i - needle.length() + 1;
    11.  }

    }

    return -1; }

/**

  • 生成next数组，（不减一的代码实现） *
  • @param next

  • @param s */ public void getNext(int[] next, String s) { // j从0开始，此时next数组初始化 int j = 0; next[0] = 0; for (int i = 1; i < s.length(); i++) {

    1.  // j要保证大于0，因为下面有取j-1作为数组下标的操作
    2.  while (j > 0 && s.charAt(i) != s.charAt(j)) {
    3.      // 查找前一位对应的回退位置
    4.      j = next[j - 1];
    5.  }
    7.  // 相等即向后移动
    8.  if (s.charAt(i) == s.charAt(j)) {
    9.      j++;
    10.  }
    12.  next[i] = j;    // 将j(前缀的长度)赋值给next[i]

    } ```

  • 前缀表减一 ```java public int strStr(String haystack, String needle) { // 先判断模式串是否为0 if (needle.length() == 0) {

    1.  return 0;

    }

    int[] next = new int[needle.length()]; getNext(next, needle); // 获取模式串的next数组

    int j = -1; // next数组中初始位置为0 for (int i = 0; i < haystack.length(); i++) {

    1.  while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
    2.      j = next[j];
    3.  }
    5.  if (haystack.charAt(i) == needle.charAt(j + 1)) {
    6.      j++;
    7.  }
    9.  if (j == needle.length() - 1) {
    10.      return i - needle.length() + 1;
    11.  }

    }

    return -1; }

/**

  • 前缀表减一的实现 *
  • @param next

  • @param s */ public void getNext(int[] next, String s) { // j从0开始，此时next数组初始化 int j = -1; next[0] = j; for (int i = 1; i < s.length(); i++) {

    1.  // j要保证大于等于0，因为下面有取j作为数组下标的操作
    2.  while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
    3.      // 查找前一位对应的回退位置
    4.      j = next[j];
    5.  }
    7.  // 相等即向后移动
    8.  if (s.charAt(i) == s.charAt(j + 1)) {
    9.      j++;
    10.  }
    12.  next[i] = j;    // 将j(前缀的长度)赋值给next[i]

    } } ```

重复的子字符串

KMP还能实现重复字符串的查找。

题目描述

力扣链接🔗

KMP算法 - 图6

题目分析

本题主要的思路是求出next数组，表示出每个数的最大前缀字符串，也就是重复的子串，那么next[len]就可以求出len位置的最大前缀字符串，如果len % (len - (next[len - 1] + 1)) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串。

代码

前缀表减一

  1. public boolean repeatedSubstringPattern(String s) {
  2.     if (s.length() == 0) {
  3.         return false;
  4.     }
  6.     int j = -1;
  7.     int len = s.length();
  8.     int[] next = new int[len];
  9.     next[0] = j;
  10.     for (int i = 1; i < len; i++) {
  11.         while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
  12.             j = next[j];
  13.         }
  15.         if (s.charAt(i) == s.charAt(j + 1)) {
  16.             j++;
  17.         }
  19.         next[i] = j;
  20.     }
  22.     // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
  23.     if (next[len - 1] > 0 && (len % (len - (next[len - 1] + 1))) == 0) {
  24.         return true;
  25.     }
  27.     return false;
  28. }

前缀表不减一

  1. public boolean repeatedSubstringPattern(String s) {
  2.     if (s.length() == 0) {
  3.         return false;
  4.     }
  6.     int len = s.length();
  7.     int j = 0;
  8.     int[] next = new int[len];
  9.     next[0] = 0;
  11.     for (int i = 1; i < len; i++) {
  12.         while (j > 0 && s.charAt(i) != s.charAt(j)) {
  13.             j = next[j - 1];
  14.         }
  16.         if (s.charAt(i) == s.charAt(j)) {
  17.             j++;
  18.         }
  20.         next[i] = j;
  21.     }
  23.     if (next[len - 1] != 0 && (len % (len - next[len - 1])) == 0) {
  24.         return true;
  25.     }
  27.     return false;
  28. }

注意：

前缀表减一和不减一的区别就是取最长相等前后缀字符串的时候有区别。

if (next[len - 1] != 0 && (len % (len - (next[len - 1] + 1))) == 0) ，减一的前缀表要加一才是最大的前后缀字符串。