题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。

如果不存在，则返回 -1 。

问题分析

字符串搜索（匹配子串）是一个很经典也具有实际应用场景的问题。

针对不同难度定位（数据范围）有不同的解法：

• 如果只是某道题的其中一个环节的话，我们可以直接调用语言自带的 indexOf() 方法；
• 如果是一道简单题（数据范围 ~）的话，我们可以使用「双指针」解法；
• 如果是一道中等题（数据范围 ~）的话，则是在考察我们 KMP 等字符串匹配算法。

朴素解法

枚举原串 ss 中的每个字符作为「发起点」，每次从原串的「发起点」和匹配串的「首位」开始尝试匹配：

匹配成功：返回本次匹配的原串「发起点」。

匹配失败：枚举原串的下一个「发起点」，重新尝试匹配。

代码:

class Solution {
    public int strStr(String ss, String pp) {
        int n = ss.length(), m = pp.length();
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        // 枚举原串的「发起点」
        for (int i = 0; i <= n - m; i++) {
            // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
            int a = i, b = 0;
            while (b < m && s[a] == p[b]) {
                a++;
                b++;
            }
            // 如果能够完全匹配，返回原串的「发起点」下标
            if (b == m) return i;
        }
        return -1;
    }
}

KMP算法

KMP算法一种改进的模式匹配算法，是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合 发表，KMP算法又称克努特-莫里斯-普拉特操作。

它的改进在于：每当从某个起始位置开始一趟比较后，在匹配过程中出现失配，不回溯i，而是利用已经得到的部分匹配结果，将一种假想的位置定位“指针”在模式上 向右滑动尽可能远的一段距离到某个位置后，继续按规则进行下一次的比较

比如当我们在主串下标为3匹配子串，往后继续匹配主串，在下标是10的位置主串和 子串不匹配，这个时候就要把子串往后移动到首字母相同的位置继续匹配，但其实我们中间已经匹配了很多字符了，里面是有一些额外信息在里面的。我们利用这些额外信息就可以帮我们少枚举一些东西。

KMP算法中最难的next数组的含义。

next[i]表示的就是以i为终点的后缀和从1开始的前缀相等，且相同的部分最长，这里我们默认子串下标从1开始。比如next[i]=j就表示在子串中p[1,j]=p[i-j+1,i]，这里我们用p数组暂时表示子串，这个就表示子串中下标从1到j这一段和i-j+1到i是相等的， 而且长度最长。所以下次从j+1再开始继续匹配。

next 数组的值是除当前字符外（注意不包括当前字符）的公共前后缀最长长度

求next数组最重要的一点是找最长公共前后缀，什么是前后缀呢

前缀是除了最后一个字符的所有子串。

后缀是除了第一个字符的所有子串。

举个栗子

比如子串是ababababab，我们求他的next数组,子串下标从1开始

很明显next[1]=0，因为第一个默认是0

next[2]=0,因为没有公共前后缀

next[3]=1，最长公共前后缀是a

next[4]=2,最长公共前后缀是ab

Next[5]=3,最长公共前后缀是aba，依次类推next[6]=4.....

我们可以发现next数组的值就是子串退回时的下标

public class Solution {
    public static int[] getNext(String ps) {
        char[] p = ps.toCharArray();
        int[] next = new int[p.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < p.length - 1) {
            if (k == -1 || p[j] == p[k]) {
                next[++j] = ++k;
            } else {
                k = next[k];
            }
        }
        return next;
    }

    public static int KMP(String ts, String ps) {
        char[] t = ts.toCharArray();
        char[] p = ps.toCharArray();
        int i = 0; // 主串的位置
        int j = 0; // 模式串的位置
        int[] next = getNext(ps);
        while (i < t.length && j < p.length) {
            if (j == -1 || t[i] == p[j]) { 
                // 当j为-1时，要移动的是i，当然j也要归0
                i++;
                j++;
            } else {
                // i不需要回溯了
                // i = i - j + 1;
                j = next[j]; // j回到指定位置
            }
        }
        if (j == p.length) {
            return i - j;
        } else {
            return -1;
        }
    }
}