leetcode 第 28 题实现 strStr()

概述

暑假期间，腆着脸皮面了字节跳动的暑期夏令营活动，被虐很惨，发现好多基础的算法题目都已经忘记了，而基本上笔试和面试考察的都是算法、操作系统等计算机基础知识。因此在后续的学习过程中，需要调整重点，将自己的精力放到刷题上面来，毕竟下半学期如果要出去实习算法和操作系统等基础知识是不可或缺的。

闲话少叙，下边来看下 leetcode 的第 28 题，具体题目如下：

 实现 strStr() 函数。
 
 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 
 示例 1:
 
 输入: haystack = "hello", needle = "ll"
 输出: 2
 示例 2:
 
 输入: haystack = "aaaaa", needle = "bba"
 输出: -1
 说明:
 
 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 
 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
 

分析

该问题一看就是一个传统字符串匹配问题，最容易想到的方法，可能就是一个双层的 for 循环。让目标字符串不断和源字符串进行比较，寻找到能够匹配目标字符串的位置。

双层 for 循环

因此我们可以实现出下边的代码：

public static int subStr(String haystack, String needle) {
    if (haystack == "" || haystack == null) {
      return -1;
    }
    int i = 0, j = 0;
    // 转化成数组进行处理
    char hayStringArry[] = haystack.toCharArray();
    char needleArry[] = needle.toCharArray();
    for (i = 0; i <= hayStringArry.length - needleArry.length; i++) {
      for (j = 0; j < needleArry.length; j++) {
        if (hayStringArry[i + j] != needleArry[j]) {
          break;
        }
      }
      if (j == needle.length()) {
        return i;
      }
    }
    return -1;
}

上边的代码很明显时间复杂度是 O(m*n)，其中 m 指的是源字符串 haystack 的长度，n 表示的是目标字符串 needle 的长度。

很明显这个算法不是最优解，我们考虑如何对其进行优化。首先我们思考，该算法时间复杂度比较高的原因主要是这两层 for循环，因此我们考虑能否通过一次 for 循环就得出结果那？

此时我们想到了《数据结构》这门课中讲的一个算法--简单的模式匹配算法。

简单的模式匹配算法

该算法主要思想如下：

从源字符串的第一个字符串开始逐个与目标字符串（待匹配的字符串）进行比较，如果相等，则继续逐个向后比较字符，直到目标字符串依次和源字符串比较完成，则称为匹配成功；如果比较过程中有某对字符不相等，则从源字符串的下一个字符起重新和目标字符串的第一个字符进行比较。如果源字符串在比较完成后仍然没有匹配成功，则称为匹配失败。

进而我们可以设计出字符的匹配算法如下：

public int strStr(String haystack, String needle) {
        if (haystack == null) {
        return -1;
        }
        char hayStackArry[] = haystack.toCharArray();
        char needleArry[] = needle.toCharArray();
        // 记录长度，减少length()函数的调用次数
        int hayStackLength = haystack.length();
        int needleLength = needle.length();
        int i = 0, j = 0;
        // i,j分别指向源字符串和目标字符
        while (i < hayStackLength && j < needleLength) {
        if (hayStackArry[i] == needleArry[j]) {
            i++;
            j++;
        } else {
            // 回退到下次进行匹配的字符串位置
            i = i - j + 1;
            // 从目标字符串的第一个位置开始进行匹配
            j = 0;
        }
        }
        if (j > needleLength - 1) {
        return i - needleLength;
        } else {
        return -1;
        }
}

我们分析该算法的时间复杂度，我们发现，虽然我们使用了单层循环，但我们发现由于 j 不断的回退，从而在坏情况下该算法的时间复杂度也可能达到 O(m*n)因此，我们考虑能否减少 j 的回退次数。此时我们考虑引入 KMP 算法。

KMP 算法

KMP 算法基本思想是这样的：较之于简单模式匹配算法其改进在于，每当一次匹配过程中出现的字符不相等的时候，不需要回溯 j 指针，而是通过已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的距离，继续进行比较。

因此，KMP 算法分成了两部分，第一部分是 next 数组的求解，第二部分是字符串匹配。

字符串匹配

KMP 算法的核心之一在于 next 数组，但在了解 next 数组的意义之前，我们首先要了解一个叫做部分匹配表(Partial Match Table)表的东西。

对于字符串"abababca"，其 PMT 如下表所示

我先解释一下字符串的前缀和后缀。如果字符串 A 和 B，存在 A=BS，其中 S 是任意的非空字符串，那就称 B 为 A 的前缀。例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。同样可以定义后缀 A=SB， 其中 S 是任意的非空字符串，那就称 B 为 A 的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。要注意的是，字符串本身并不是自己的后缀。

有了这个定义，就可以说明 PMT 中的值的意义了。PMT 中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如，对于”aba”，它的前缀集合为{”a”, ”ab”}，后缀 集合为{”ba”, ”a”}。两个集合的交集为{”a”}，那么长度最长的元素就是字符串”a”了，长 度为 1，所以对于”aba”而言，它在 PMT 表中对应的值就是 1。再比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}， 两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为 3。 好了，解释清楚这个表是什么之后，我们再来看如何使用这个表来加速字符串的查找，以及这样用的道理是什么。如图 1.12 所示，要在主字符串"ababababca"中查找模式字符串"abababca"。如果在 j 处字符不匹配，那么由于前边所说的模式字符串 PMT 的性质，主字符串中 i 指针之前的 PMT[j −1] 位就一定与模式字符串的第 0 位至第 PMT[j−1] 位是相同的。这是因为主字符串在 i 位失配，也就意味着主字符串从 i−j 到 i 这一段是与模式字符串的 0 到 j 这一段是完全相同的。而我们上面也解释了，模式字符串从 0 到 j−1 ，在这个例子中就是”ababab”，其前缀集合与后缀集合的交集的最长元素为”abab”， 长度为 4。所以就可以断言，主字符串中 i 指针之前的 4 位一定与模式字符串的第 0 位至第 4 位是相同的，即长度为 4 的后缀与前缀相同。这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持 i 指针不动，然后将 j 指针指向模式字符串的 PMT[j −1]位即可。

简言之，以图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边 6 位就是相同的。又因为模式字符串的前 6 位，它的前 4 位前缀和后 4 位后缀是相同的，所以我们推知主字符串 i 之前的 4 位和模式字符串开头的 4 位是相同的。就是图中的灰色部分。那这部分就不用再比较了。

有了上面的思路，我们就可以使用 PMT 加速字符串的查找了。我们看到如果是在 j 位 失配，那么影响 j 指针回溯的位置的其实是第 j −1 位的 PMT 值，所以为了编程的方便， 我们不直接使用 PMT 数组，而是将 PMT 数组向后偏移一位。我们把新得到的这个数组称为 next 数组。下面给出根据 next 数组进行字符串匹配加速的字符串匹配程序。其中要注意的一个技巧是，在把 PMT 进行向右偏移时，第 0 位的值，我们将其设成了-1，这只是为了编程的方便，并没有其他的意义。在本节的例子中，next 数组如下表所示。

因此 KMP 算法的匹配代码如下:

public static int kmp(String haystack, String needle) {
    char[] needleArry = needle.toCharArray();
    char[] haystackArry = haystack.toCharArray();
    int needleLength = needle.length();
    int haystackLength = haystack.length();
    int[] next = getNext(needleArry);
    int i = 0, j = 0;
    while (i < haystackLength && j < needleLength) {
      if (j == -1 || haystackArry[i] == needleArry[j]) {
        i++;
        j++;
      } else {
        j = next[j];
      }
    }
    if (j > needleLength - 1) {
      return i - needleLength;
    } else {
      return -1;
    }
  }

next 数组求解

前边我们讲了 kmp 算法的匹配过程，下边我们主要讲一下 next 数组的求解过程。其实简单来说 next 数组的求解过程完全可能一个字符串的匹配过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的 next 值就是匹配 成功的字符串的长度。

其匹配过程的具体代码如下：

  // 生成next数组
  private static int[] getNext(char[] needleArry) {
    int next[] = new int[needleArry.length + 1];
    next[0] = -1;
    int i = 0, j = -1;
    while (i < needleArry.length) {
      if (j == -1 || needleArry[i] == needleArry[j]) {
        i++;
        j++;
        next[i] = j;
      } else {
        j = next[j];
      }
    }
    return next;
  }

虽然说 KMP 算法已经十分好了，但实际在程序设计中很少直接 kmp 算法来直接求解，更多的会使用 BM 算法以及 Sunday 算法。因为这两个算法较之于 KMP 算法，它会更快。

Sunday 算法

Sunday 算法某种程度算法 BM 算法的改良，而且效果更好，因此主要考虑使用 Sunday 算法解决一下该问题。由于篇幅原因本片文章就不再详解，感兴趣的话可以看笔者的另一篇文章--《使用 sunday 算法解决字符串匹配问题》

参考

1. https://www.zhihu.com/question/21923021
2. https://www.jianshu.com/p/2e6eb7386cd3