Leetcode经典题15-- 找出字符串中第一个匹配项的下标（KMP）

题目描述：

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

输入输出示例：

输入：haystack = "sadbutsad", needle = "sad"

输出：0

解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。

解决方案

方式一：暴力求解法 （较优解）

算法思想：直观的解法的是：枚举原串 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;
    }
}

复杂度分析

时间复杂度：n 为原串的长度，m 为匹配串的长度。其中枚举的复杂度为 O(n−m)，构造和比较字符串的复杂度为 O(m)。整体复杂度为 O((n−m)∗m)。

空间复杂度：O(1)。

方式二：KMP算法

KMP算法-----大串当中找小串

KMP：找最长相等的前后缀组成的前缀表 O(m+n)

1.前缀和后缀

前缀：不包含最后一个字符的所有以第一个字符开头的连续字符串

后缀：不包含第一个字符的所有以最后一个字符结尾的连续字符串

2.找最长相等的前后缀组成的前缀表

3.KMP算法执行过程

第一步:两个游标从前向后进行变量，并且比较值是否相等，如果相等执行i++j++。

如果不相等，那么则和暴力解法不—致!

第二步:如果我们此时能够让i游标不动，同时j游标指向b是最好的。

如何指向b?

1.找前缀，后缀

2.找到最长相等前后缀的长度

3.利用前缀表重新匹配并构造next数组

很多KMP算法的实现都是使用next数组来做回退操作，那么next数组与前缀表有什么关系呢?

next数组就可以是前缀表，但是很多实现都是把前缀表统一减一(右移一位，初始位置为-1)之后作为next数组。

这并不涉及到KMP的原理，而是具体实现，next数组既可以就是前缀表，也可以是前缀表统一减一(右移一位，初始位置为-1)

next数组的构建过程

j=next[j-1] :将j指针返回到上一次最长相等前缀的末尾，再逐渐缩短前缀的长度，看是否能找到公共前缀，否则，将next数组的对应位置置0

第三步：

寻找匹配的下标

首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在，则跳转到「前缀」的下一个位置继续往下匹配：

跳转到下一匹配位置后，尝试匹配，发现两个指针的字符对不上，并且此时匹配串指针前面不存在相同的「前缀」和「后缀」，这时候只能回到匹配串的起始位置重新开始：

代码实现：

class Solution {
    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;
        
        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m + 1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }

        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m;
        }

        return -1;
    }
}

复杂度分析：

时间复杂度：n 为原串的长度，m 为匹配串的长度。复杂度为 O(m+n)。

空间复杂度：构建了 next 数组。复杂度为 O(m)。

本文章主要参考Leetcode中宫水三叶老师的解法