【算法】实现indexOf()函数(KMP)|江阴雨辰互联

2023年7月20日发(作者：)

【算法】实现indexOf（）函数（KMP）题⽬实现 indexOf() 函数。给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第⼀个位置（下标从 0 开始）。如果不存在，则返回 -1 。说明：当 needle 是空字符串时，我们应当返回什么值呢？这是⼀个在⾯试中很好的问题。对于本题⽽⾔，当 needle 是空字符串时我们应当返回 0 。这与 C 语⾔的 strstr() 以及 Java 的 indexOf() 定义相符。⽰例 1：输⼊：haystack = “hello”, needle = “ll”输出：2⽰例 2：输⼊：haystack = “aaaaa”, needle = “bba”输出：-1⽰例 3：输⼊：haystack = “”, needle = “”输出：0提⽰：0 <= , <= 5 * 104haystack 和 needle 仅由⼩写英⽂字符组成朴素匹配直观的解法的是：枚举原串 ss 中的每个字符作为「发起点」，每次从原串的「发起点」和匹配串的「⾸位」开始尝试匹配：匹配成功：返回本次匹配的原串「发起点」。匹配失败：枚举原串的下⼀个「发起点」，重新尝试匹配时间复杂度 O(m * n)实现class Solution { public int strStr(String haystack, String needle) { int n = (), m = (); //

枚举原串的「发起点」 for (int i = 0; i < n - m + 1; i++) { boolean flag = true; //

从原串的「发起点」和匹配串的「⾸位」开始，尝试匹配 for (int j = 0; j < m; j++) { if ((i + j) != (j)) { flag = false; break; } } //

如果能够完全匹配，返回原串的「发起点」下标 if (flag) return i; } return -1; }}KMP解法KMP 算法是⼀个快速查找匹配串的算法，它的作⽤其实就是本题问题：如何快速在「原字符串」中找到「匹配字符串」。KMP的经典思想就是:当出现字符串不匹配时，可以记录⼀部分之前已经匹配的⽂本内容，利⽤这些信息避免从头再去做匹配。时间复杂度O(m+n)先看下「朴素匹配」逻辑：1. 将原串的指针移动⾄本次「发起点」的下⼀个位置（b 字符处）；匹配串的指针移动⾄起始位置。2. 尝试匹配，发现对不上，原串的指针会⼀直往后移动，直到能够与匹配串对上位置也就是说，对于「朴素匹配」⽽⾔，⼀旦匹配失败，将会将原串指针调整⾄下⼀个「发起点」，匹配串的指针调整⾄起始位置，然后重新尝试匹配。然后我们再看看「KMP 匹配」过程：1. ⾸先匹配串会检查之前已经匹配成功的部分中⾥是否存在相同的「前缀」和「后缀」。如果存在，则跳转到「前缀」的下⼀个位置继续往下匹配2. 跳转到下⼀匹配位置后，尝试匹配，发现两个指针的字符对不上，并且此时匹配串指针前⾯不存在相同的「前缀」和「后缀」，这时候只能回到匹配串的起始位置重新开始到这⾥，你应该清楚 KMP 为什么相⽐于朴素解法更快：因为 KMP 利⽤已匹配部分中相同的「前缀」和「后缀」来加速下⼀次的匹配。因为 KMP 的原串指针不会进⾏回溯（没有朴素匹配中回到下⼀个「发起点」的过程）。可以预处理出

next 数组，数组中每个位置的值就是该下标应该跳转的⽬标位置（

next 点）。在实际编码时，通常我会往原串和匹配串头部追加⼀个空格（哨兵）。⽬的是让

j 下标从

0 开始，省去

j 从

-1 开始的⿇烦。//

构建 next

数组，数组长度为匹配串的长度（next

数组是和匹配串相关的）int[] next = new int[m + 1];//

构造过程 i = 2，j = 0

开始，i

⼩于等于匹配串长度