实现 strStr()

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

分析

初步思考

如果我们查询的子串比父串的长度还长，那么自然不存在这个这个下标，返回-1。

如果我们子串和父串一样，则直接返回下标0；

遍历haystack的字符如果和我们needle的首字符相同，则截取haystack的长度和needle的长度一致，截取的结果和needle做对比，相同则返回下标。不同继续遍历。

public static int strStr(String haystack, String needle) {
       if (needle.length() > haystack.length()) {
            return -1;
       }
        if (needle.equals(haystack)) {
          return 0;
        }
        for (int i = 0; i < haystack.length(); i++) {
            if (needle.charAt(0) == haystack.charAt(i) && haystack.length() >= i + needle.length() && haystack.substring(i, i + needle.length()).equals(needle)) {
                return i;
            }
        }
       return -1;
    }

继续思考

看到这个题，想到大学数据结构的一个算法就是KMP算法。就是每次匹配完移动的时候，不用一个一个向后移动，而是先算出真前缀的长度。如果不符合就直接跳到下一个前缀的位置。

1.1 父串ABCABCDACBCE子串ABCE

首先我们以下图父串ABCABCDACBCE子串ABCE为例，我们从左往右遍历，当发现不一样的元素的时候，我们根据我们子串中的前后缀长度进行跳转。我们怎么找呢？

在ABCE这个字符串中

• 先计算AB,前缀A不对应后缀B，为0
• 再计算ABC，我们知道上一个AB为0，我们只需要计算前缀A不对应后缀C，还是为0
• 最后计算ABCE,我们知道上一个ABC为0，我们只需要计算前缀A不对应后缀E，还是为0

所以这个子串的没有最长前后缀，我们把它放在数组就是Arr[0,0,0,0]。

当我们遍历到下图位置i=3,j=3时。父串的字符和子串不相等，我们只需要保持父串不动，子串回到上一个数组Arr[j=2]的位置0

也就是下图，父串指针不变，子串指针回到首位值。

1.2父串ABCABCAABCE子串ABCAA

再举个例子，父串ABCABCAABCE子串ABCAA。

先计算子串的最大前后缀

• 子串AB,A不对应后缀B ，为0
• 子串ABC，上一个为0，则比较前缀A不对应后缀C,为0
• 子串ABCA,上一个为0，前缀A对应后缀A，则为1
• 子串ABCAA,上一个为1，前缀B不对应后缀A，则前缀回退回A.前缀A对应后缀A，则还是1

所以最大前后缀数组Arr[0,0,0,1,1]

我们对比完i=4,j=4,此时不相等，则父串指针不动，子串回退到Arr[j=3]=1。

也就是如下图所示。

我们继续对比

2.1父串ABCABCDACBCE子串ABCE

第二次对比完i=6,j=3,此时不一样，我么父串指针不变，子串指针回退到Arr[j=2]=0

回退之后，如下图所示。此时对比不一样，我们i++

2.2父串ABCABCAABCE子串ABCAA

遍历完，我们找到了结果。就无需计算最大前后缀了。

3.1父串ABCABCDACBCE子串ABCE

遍历完，我们找到了结果。就无需计算最大前后缀了。

答案

所以这个题的关键就是用代码找到子串的最大前后缀。以便下次我们调整移动子串的位置，减少遍历的次数。

    public static int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }

复杂度

• 时间复杂度：O(n+m)，其中 nn 是字符串 haystack 的长度，mm 是字符串needle 的长度
• 空间复杂度：O(m)，其中 m 是字符串needle的长度。

总结

KMP算法，我记得考研那会就是经常考的题型之一。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。不会的兄弟们，学起来吧。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！