$needle$ $in$ $haystack$

$中译：大海捞针$

JAVA

① 直接调用（0ms）

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

② 暴力（0ms）

class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length(), n = needle.length();
        if (n == 0) return 0;
        for (int i = 0; i < m - n + 1; ++i) {
            if (haystack.substring(i, i + n).equals(needle))	//substring 返回字符串的子字符串
                return i;
        }
        return -1;
    }
}

③ Rabin Karp（4ms）【时间复杂度：$O(NlogN)$ 空间复杂度：$O(logN)$】

class Solution {
    public int charToInt(int idx, String str) {
        return (int) str.charAt(idx) - (int) 'a';
    }

    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (n < m) return -1;
        if (m == 0) return 0;

        int a = 26;     // 字符集的个数
        long mod = (long) Math.pow(2, 31);      // 记住要用 long      // mod一般是固定的

        long h = 0, res_h = 0;                  // 记住要用 long
        for (int i = 0; i < m; ++i) {
            h = (h * a + charToInt(i, haystack)) % mod;
            res_h = (res_h * a + charToInt(i, needle)) % mod;
        }
        if (h == res_h) return 0;

        long mod_a = 1;
        for (int i = 0; i < m; ++i) mod_a = (mod_a * a) % mod;
        for (int i = 1; i < n - m + 1; ++i) {       // 有减号时最好加上mod
            h = (h * a - charToInt(i - 1, haystack) * mod_a
                    + charToInt(m + i - 1, haystack) + mod) % mod;
            if (h == res_h) return i;
        }
        return -1;
    }
}

其实我不明白为什么这种方法名叫 $RabinKarp$，我觉得用 滚动哈希 更贴切

官方题解讲的非常好理解，我就补充一句话：因为题目中只会出现小写的英文字母，所以 a = 26，其代表的是字符集的个数

④ 其他方法 粗略讲解（无代码）

一、Sunday 算法
参考文章

简单来说就是跳跃性匹配，以匹配串 $checkthisout$ 和子串 $this$ 演示

checkthisout
this			//显然不匹配

检查匹配串的下一位字符k是否在子串中，如果不在就一整个跳过，直接跳跃到k后面匹配

checkthisout
     this		// 匹配成功

要是k在子串中怎么办？那就不能一整个跳过了，跳跃的位数由偏移表决定

偏移表的作用是存储每一个在匹配串中出现的字符，偏移位等于子串长度减去字符下标，例如 $aab$：

• a 的偏移位就是 len(pattern) - 1 = 2（取第二个 a 计算）
• b 的偏移位就是 len(pattern) - 2 = 1
• 不存在的字符均为 len(pattern) + 1 = 4

举个例子

substringsea
sea				//匹配不成功

偏移量为 3，向右移动 3 位

substringsea
   sea			//匹配不成功

偏移量为 4，向右移动 4 位

substringsea
       sea		//匹配不成功

偏移量为 2，向右移动 2 位

substringsea
         sea	//匹配成功

二、BM 算法
1.参考文章
2.参考文章
3.参考文章

这个算法也是跳跃性匹配，但是它有两种跳跃的方法，分别是坏字符和好后缀，跳跃的位数取这两种方法计算的最大者，下面看具体运用

坏字符

将匹配串和子串对齐后，从最后一位开始对比，若匹配字符相同则往前继续匹配，若匹配字符失败则称匹配串的那个字符 $a$ 为坏字符，从子串匹配失败的那个字符前面寻找是否存在 $a$，若不存在则直接偏移子串的长度的量（len(子串)），若子串的坏字符移动到匹配串的坏字符的位移量即偏移量

abcadabd
abd			// 匹配不成功

坏字符为 c, 偏移量为 3，向右移动 3 位

abcadabd
   abd		// 匹配不成功

坏字符为 a, 偏移量为 2，向右移动 2 位

abcadabd
     abd	// 匹配成功

其实可以用哈希表记录子串的字符和下标， 这样就可以快速定位字符的位置

假设我们现在有这样一个匹配串 $aaaaaaaaaaaaa$，模式串为 $baaa$，我们用坏字符规则来处理， 好了，计算出来在模式串中的坏字符位置为 $-1$，所以，光凭坏字符是不够的，我们需要另一种处理方式，即：好后缀

好后缀

好后缀也分为完全匹配和部分匹配，具体如下

完全匹配，指匹配串与子串对齐后，从后往前一直匹配，最长的相同后缀就是好后缀，再往前找，直到找出子串的另一个好后缀，将这个好后缀和匹配串的好后缀对齐，此偏移量即完全匹配的偏移量

部分匹配，指比较匹配串的后缀和子串的前缀，当二者存在相同的字符串时，此字符串为好后缀，将子串的前缀和匹配串的后缀对齐，此偏移量即部分匹配的偏移量

只有在完全匹配不成功时，再进行部分匹配，若都不成功则直接偏移子串的长度的量（len(子串)）

abcabcabab
cabab		// 匹配不成功

好后缀为 ab, 子串前面存在 ab, 故偏移量为 2, 完全匹配

abcabcabab
  cabab		// 匹配不成功

完全匹配无好后缀, 但匹配位置的后缀和子串的前缀相同, 好后缀为 ca, 故偏移量为 3, 部分匹配

abcabcabab
     cabab	// 匹配成功

一般要引入 suffix 数组 和 prefix 数组用于 记录前缀子串 和 是否能成功匹配

三、Horspool 算法
1.参考文章
2.参考文章

感觉是和 Sunday 算法很相似的算法，甚至和 km 算法的坏字符也非常相似，就是简单的判断 + 偏移，建议仔细看看上面的 2.参考文章，看完基本就理解了

四、KMP 算法

我直接推荐 死嗑 KMP 算法，先看上面的视频，再做下面的习题就差不多明白 （其实自己什么都不懂） 了

Python

① 直接调用（48ms）

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

② 暴力（24ms）

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        for i in range(n-m+1):
            if(haystack[i:i+m]) == needle:
                return i
        return -1

③ Rabin Karp（44ms）

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        L, n = len(needle), len(haystack)
        if L > n:
            return -1
        if L == 0:
            return 0

        a = 26
        modulus = 2**31

        # 值得学习的操作
        def h_to_int(i): return ord(haystack[i]) - ord('a')		# ord 返回值是对应的十进制整数
        def needle_to_int(i): return ord(needle[i]) - ord('a')

        h = ref_h = 0
        for i in range(L):
            h = (h * a + h_to_int(i)) % modulus
            ref_h = (ref_h * a + needle_to_int(i)) % modulus
        if h == ref_h:
            return 0

        aL = pow(a, L, modulus)
        for start in range(1, n - L + 1):
            h = (h * a - h_to_int(start - 1) * aL +
                 h_to_int(start + L - 1)) % modulus
            if h == ref_h:
                return start

        return -1