【KMP算法, Rabin-Karp算法, 快速幂】找出字符串中第一个匹配项的下标

题目

28. 找出字符串中第一个匹配项的下标

---

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

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 10^4
• haystack 和 needle 仅由小写英文字符组成

解题

方法一：KMP算法

思路

KMP 算法。

KMP 算法

转载自：代码随想录 - 字符串 - 实现strStr()

什么是KMP

说到 KMP，先说一下 KMP 这个名字是怎么来的，为什么叫做 KMP 算法呢。
因为是由这三位学者发明的：Knuth，Morris 和 Pratt，所以取了三位学者名字的首字母，叫做 KMP 算法。

KMP有什么用

KMP 主要应用在字符串匹配上。

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

所以如何记录已经匹配的文本内容，是KMP的重点，也是 next 数组肩负的重任。

什么是前缀表

写过 KMP 的同学，一定都写过 next 数组，那么这个 next 数组究竟是个啥呢？
next数组就是一个前缀表（prefix table）。

前缀表有什么作用呢？
——前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

为了清楚的了解前缀表的来历，我们来举一个例子：
要在文本串：str = "aabaabaafa" 中查找是否出现过一个模式串：pat = "aabaaf"。
如动画所示：

动画里，我特意把 子串 "aa" 标记上了，这是有原因的，大家先注意一下，后面还会说道。

可以看出，文本串中第六个字符 'b' 和 模式串的第六个字符 'f'，不匹配了。如果暴力匹配，会发现不匹配，此时就要从头匹配了。但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符 'b'继续开始匹配。

此时就要问了：前缀表是如何记录的呢？
首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。
那么前缀表就是：记录下标 i 及其之前的字符串中，有多大长度的相同前缀后缀。

最长公共前后缀？

首先明确定义：

• 文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串，即真前缀，比如说 s = "abcd"，那么 "a"、"ab"、"abc" 都是 s 的前缀，而 "abcd"（也就是它本身）不能算作 s 的前缀。
• 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串，即真后缀，同样比如： s = "abcd"，那么 "d"、"cd"、"bcd" 都是 s 的后缀，而 "abcd"（也就是它本身）不能算作 s 的后缀。

正确理解什么是前缀、什么是后缀很重要！

那么网上清一色都说「kmp 最长公共前后缀」又是什么回事呢？
我查了一遍 算法导论 和 算法4 里 KMP 的章节，都没有提到 “最长公共前后缀” 这个词，也不知道从哪里来了，我理解是用“最长相等前后缀” 更准确一些，**因为前缀表要求的就是相同前后缀的长度。**而最长公共前后缀里面的 “公共”，更像是说前缀和后缀公共的长度。这其实并不是前缀表所需要的。所以按照这个定义：

• 字符串 "a" 的最长相等前后缀为 $0$。
• 字符串 "aa" 的最长相等前后缀为 $1$。
• 字符串 "aaa" 的最长相等前后缀为 $2$。
• 等等……

为什么一定要用前缀表

前缀表为啥能告诉我们上次匹配的位置，并跳过去呢？
——回顾一下，刚刚匹配的过程在下标 $5$ 的地方遇到不匹配，模式串是指向 'f'，如图：

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

**下标 $5$ 之前这部分的字符串（也就是字符串 "aabaa"）的最长相等的前缀和后缀字符串是子字符串 "aa" ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了。**所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

如何计算前缀表

如图，长度为前 $1$ 个字符的子串 "a"，最长相同前后缀的长度为 $0$：

长度为前 $2$ 个字符的子串 "aa"，最长相同前后缀的长度为 $1$：

长度为前 $3$ 个字符的子串 "aab"，最长相同前后缀的长度为 $0$：

以此类推：

• 长度为前 $4$ 个字符的子串 "aaba"，最长相同前后缀的长度为 $1$。
• 长度为前 $5$ 个字符的子串 "aabaa"，最长相同前后缀的长度为 $2$。
• 长度为前 $6$ 个字符的子串 "aabaaf"，最长相同前后缀的长度为 $0$。

那么把求得的最长相同前后缀的长度就是对应前缀表的元素，如图：

可以看出模式串与前缀表对应位置的数字表示的就是：下标 i 及其之前的字符串中，有多大长度的相同前缀后缀。

再来看一下如何利用前缀表找到当字符不匹配的时候应该指针应该移动的位置，如动画所示：

找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。
为什么要前一个字符的前缀表的数值呢？
—— 因为要找前面字符串的最长相同的前缀和后缀，所以要看前一位的 前缀表的数值。

前一个字符的前缀表的数值是2， 所有把下标移动到下标2的位置继续比配。最后就在文本串中找到了和模式串匹配的子串了。

前缀表与 next 数组

很多 KMP 算法的实现都是使用 next 数组来做回退操作，那么 next 数组与前缀表有什么关系呢？
—— next 数组可以就是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为 -1）之后作为 next 数 组。

为什么这么做呢？
——其实这并不涉及到 KMP 的原理，而是具体实现，next 数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为 -1，后面我会提供两种不同的实现代码，大家就明白了。

使用 next 数组来匹配

以下我们以前缀表统一减一之后的next数组来做演示。

有了 next 数组，就可以根据 next 数组来匹配文本串 s，和模式串 t 了（注意 next 数组是前缀表统一右移一位 next[0] = -1 后的）。

匹配过程动画如下：

时间复杂度分析

其中 n 为文本串长度，m 为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是$O(n)$，之前还要单独生成 next 数组，时间复杂度是 $O(m)$。所以整个 KMP 算法的时间复杂度是 $O(n+m)$。

暴力的解法显而易见是$O(n \times m)$，所以KMP在字符串匹配中极大的提高了搜索的效率。

代码实现

构造 next 数组

我们定义一个函数 get_next() 来构建 next 数组，函数参数为模式串(pat)，返回 next 数组。 代码如下：

vector<int> get_next(const string& pat)

构造 next 数组其实就是计算模式串 pat 的前缀表的过程。 主要有如下三步：

1. 初始化：
   定义两个指针 i 和 j，i 指向后缀末尾位置，j 指向前缀末尾位置。
   然后还要对 next 数组进行初始化赋值，如下：

   int m = pat.size();
   int i = 1, j = -1;
   vector<int> nexts(m);
   nexts[0] = j;
   

   j 为什么要初始化为 -1 呢？
   ——因为之前说过：前缀表要统一减一的操作仅仅是其中的一种实现，我们这里选择 j 初始化为 -1，下文我还会给出 j 不初始化为 -1 的实现代码。

   nexts[i] 表示 i 及其之前最长相等的前后缀长度（其实就是 j），所以初始化 nexts[0] = j。

2. 处理前后缀不相同的情况：

   因为 j 初始化为-1，那么 i 就从1开始，进行 pat[i] 与 pat[j+1] 的比较，所以遍历模式串 pat 的循环下标 i 要从 $1$ 开始：

   for (; i < m; ++i)
   

   如果 pat[i] 与 pat[j+1] 不相同，也就是遇到前后缀末尾不同的情况，就要向前回退。

   怎么回退呢？
   ——nexts[j] 就记录着 j 及其之前的子串的相同前后缀的长度。

   那么 pat[i] 与 pat[j+1] 不相同，就要找 j+1 前一个元素在 nexts 数组里的值（就是 nexts[j]）。

   所以，处理前后缀不相同的情况代码如下：

   while (j >= 0 && pat[i] != pat[j + 1]) j = nexts[j]; // 前后缀不相同了 向前回退
   

3. 处理前后缀相同的情况：
   如果 s[i] 与 s[j + 1] 相同，那么就同时向后移动 i 和 j 说明找到了相同的前后缀，同时还要将 j（前缀的长度）赋给 nexts[i] ，因为 nexts[i] 要记录相同前后缀的长度：

   if (pat[i] == pat[j + 1]) ++j; // 找到相同的前后缀
   nexts[i] = j;
   

最后整体构建 next 数组的函数代码如下：

vector<int> get_next(const string& pat) {
    int m = pat.size();
    int i = 1, j = -1;
    vector<int> nexts(m);
    nexts[0] = j;
    for (; i < m; ++i) {
    	while (j >= 0 && pat[i] != pat[j + 1]) j = nexts[j]; // 前后缀不相同了 向前回退
        if (pat[i] == pat[j + 1]) ++j; // 找到相同的前后缀
		nexts[i] = j;
    }
    return nexts;
}

构造 next 数组的逻辑流程动画如下：

使用next数组来做匹配

在文本串 str 里找是否出现过模式串 pat。

初始化两个下标 j 指向模式串起始位置，i 指向文本串起始位置。

那么 j 初始值依然为 -1，为什么呢？
——依然因为 nexts 数组里记录的起始位置为 -1。

i 就从 $0$ 开始，遍历文本串：

int n = str.size(), m = pat.size();
for (int i = 0, j = -1; i < n; ++i)

接下来就是 str[i] 与 pat[j + 1] （因为 j 是从 -1 开始的） 进行比较。

如果 str[i] 与 pat[j + 1] 不相同，j 就要从 nexts 数组里寻找下一个匹配的位置：

while(j >= 0 && str[i] != pat[j + 1]) j = nexts[j];

如果 str[i] 与 pat[j + 1] 相同，那么 i 和 j 同时向后移动：

if (str[i] == pat[j + 1]) ++j;

如何判断在文本串 str 里出现了模式串 pat 呢，如果 j 指向了模式串 pat 的末尾，那么就说明模式串 pat 完全匹配文本串 str 里的某个子串了。

本题要在文本串字符串中找出模式串出现的第一个位置 (从 $0$ 开始)，所以返回当前在文本串匹配模式串的位置 i 减去模式串的长度，就是文本串字符串中出现模式串的第一个位置：

if (j + 1 == m) return i - j;

那么使用 next 数组，用模式串匹配文本串的整体代码如下：

int n = str.size(), m = pat.size();
for (int i = 0, j = -1; i < n; ++i) {
    while(j >= 0 && str[i] != pat[j + 1]) j = nexts[j];
    if (str[i] == pat[j + 1]) ++j;
    if (j + 1 == m) return i - j;
}

代码

next 数组为前缀表右移一位：

class Solution {
    public int strStr(String haystack, String needle) {
        char[] str = haystack.toCharArray(), pat = needle.toCharArray();
        int n = str.length, m = pat.length;
        int[] nexts = new int[m];
        nexts[0] = -1;
        for (int i = 1, j = -1; i < m; ++i) {
            while (j >= 0 && pat[j + 1] != pat[i]) j = nexts[j];
            if (pat[j + 1] == pat[i]) ++j;
            nexts[i] = j;
        }
        for (int i = 0, j = -1; i < n; ++i) {
            while (j >= 0 && pat[j + 1] != str[i]) j = nexts[j];
            if (pat[j + 1] == str[i]) ++j;
            if (j + 1 == m) return i - j;
        }
        return -1;
    }
}

class Solution {
    vector<int> get_next(const string& pat) {
        int m = pat.size();
        int i = 1, j = -1;
        vector<int> nexts(m);
        nexts[0] = j;
        for (; i < m; ++i) {
            while (j >= 0 && pat[i] != pat[j + 1]) j = nexts[j];
            if (pat[i] == pat[j + 1]) ++j;
            nexts[i] = j;
        }
        return nexts;
    }

public:
    int strStr(string str, string pat) {
        int n = str.size(), m = pat.size();
        vector<int> nexts = get_next(pat);
        for (int i = 0, j = -1; i < n; ++i) {
            while(j >= 0 && str[i] != pat[j + 1]) j = nexts[j];
            if (str[i] == pat[j + 1]) ++j;
            if (j + 1 == m) return i - j;
        }
        return -1;
    }
};

next 数组即为前缀表不右移：

class Solution {
    vector<int> get_next(const string& pat) {
        int m = pat.size();
        int i = 1, j = 0;
        vector<int> nexts(m);
        nexts[0] = j;
        for (; i < m; ++i) {
            while (j > 0 && pat[i] != pat[j]) j = nexts[j - 1];
            if (pat[i] == pat[j]) ++j;
            nexts[i] = j;
        }
        return nexts;
    }

public:
    int strStr(string str, string pat) {
        int n = str.size(), m = pat.size();
        vector<int> nexts = get_next(pat);
        for (int i = 0, j = 0; i < n; ++i) {
            while(j > 0 && str[i] != pat[j]) j = nexts[j - 1];
            if (str[i] == pat[j]) ++j;
            if (j == m) return i - j + 1;
        }
        return -1;
    }
};

区别点：

方法二：Rabin-Karp算法 快速幂

思路

Rabin-Karp 算法。

Rabin-Karp 算法

首先看 【哈希表, 滑动哈希】重复的DNA序列「滑动哈希基础」 - 滑动哈希 可以发现就是本题的数据范围简化版（上题字符只会出现 A、C、G、T 四种，子字符串长度固定为 $10$），而本题字符会出现所有的小写英文字符 $26$ 种，子字符串长度固定且最大为 $10^4$，也就是说哈希数最大可能会到恐怖的 $26^{10^4}$。但好消息是其它地方与该题是几乎一样的，所以可以套用上面的解法，唯一需要改进的就是哈希数的计算。

解决这个问题的办法就是取模，把哈希数对一个较大的素数(MOD)取模就可以把其压缩到 $[0, MOD)$ 的范围内，但取完模之后又产生了新的问题：哈希冲突，所以不能仅凭哈希数相同就判断两字符串相同了，要在哈希相同的基础上再判断两字符串的每一个字符是否相同。

参考：滑动窗口算法延伸：Rabin Karp 字符匹配算法 - labuladong的算法小抄

代码

class Solution {
    // 小写字符映射到26进制数  取模常数10^9+7
    static final int R = 26, MOD = (int) 1e9 + 7;

    public int strStr(String str, String pat) {
        int n = str.length(), L = pat.length(); // 模式串的位数
        long RL = quickPow(R, L - 1); // R^(L-1)
        // 把原串映射并转换为数组 O(N)
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) nums[i] = str.charAt(i) - 'a';
        // 模式串哈希与窗口字串哈希
        long patHash = 0L, windowHash = 0L;
        // 算出模式串的哈希 O(L)
        for (char ch : pat.toCharArray()) patHash = (patHash * R + ch - 'a') % MOD;
        // 滑动窗口 O(N)
        int left = 0, right = 0;
        while (right < n) {
            // 扩大窗口 -> 从右边移入字符 -> 在低位增加数字
            windowHash = (windowHash * R + nums[right++]) % MOD;
            // 当子串与模式串长度相同时
            if (right - left == L) {
                // 判断字串的哈希值是否等于模式串
                // 如果相等再确认子串与模式串是否完全相同 防止哈希冲突 O(L)
                if (windowHash == patHash && str.substring(left, right).equals(pat)) return left;
                // 缩小窗口 -> 从左边移出字符 -> 在高位删除数字
                windowHash = (windowHash - RL * nums[left++] % MOD + MOD) % MOD;
                // X % Q == (X + Q) % Q 是一个模运算法则
                // 因为windowHash - RL * nums[left++] % MOD可能是负数
                // 所以额外再加一个MOD后再取一边模 保证windowHash不会是负数
            }
        }
        return -1;
    }

    // 快速幂
    long quickPow(long base, long expo) {
        long res = 1L;
        while (expo != 0) {
            if ((expo & 1) != 0) res = res * base % MOD;
            base = base * base % MOD;
            expo >>= 1;
        }
        return res;
    }
}

时间复杂度：$O(N)$。

方法三：字符串哈希

思路

把主串与模式串哈希，随后在主串中枚举长度与模式串相同的子串哈希，并与模式串哈希对比。

字符串哈希模板：哈希 - 字符串哈希。

代码

typedef unsigned long long ULL;

const int N = 1e4 + 10, P = 131;
ULL pat_hash, h[N], p[N];

class Solution {
    ULL sub_hash(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }

public:
    int strStr(string str, string pat) {
        int n = str.size(), m = pat.size();
        p[0] = 1;
        for (int i = 1; i <= n; ++i) {
            h[i] = h[i - 1] * P + str[i - 1];
            p[i] = p[i - 1] * P;
        }
        pat_hash = 0;
        for (int i = 1; i <= m; ++i) {
            pat_hash = pat_hash * P + pat[i - 1];
        }
        for (int l = 1; l <= n - m + 1; ++l) {
            if (sub_hash(l, l + m - 1) == pat_hash) return l - 1;
        }
        return -1;
    }
};