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

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

思路

这个问题可以通过使用KMP（Knuth-Morris-Pratt）算法来解决。KMP算法是一种改进的字符串匹配算法，它的主要思想是当子串与目标字符串不匹配时，能知道一部分已经匹配的字符，利用这些信息避免从目标字符串的头部再去做匹配。

解题方法

KMP算法首先会预处理子串，生成一个名为next的数组，用于存储子串的最长公共前后缀的长度。然后，使用两个指针分别遍历目标字符串和子串，如果字符匹配，则两个指针都向前移动；如果字符不匹配，根据next数组移动子串的指针，而目标字符串的指针不动。如果子串的指针移动到了子串的末尾，那么就找到了一个匹配的子串。

复杂度

时间复杂度:

$O(n+m)$，其中$n$是目标字符串的长度，$m$是子串的长度。预处理子串的时间复杂度是$O(m)$，匹配的时间复杂度是$O(n)$。

空间复杂度:

$O(m)$，需要额外的空间来存储$next$数组。

Code

class Solution {public int strStr(String s1, String s2) {return kmp(s1.toCharArray(), s2.toCharArray());}public int kmp(char[] s1, char[] s2) {int n = s1.length;int m = s2.length;int x = 0, y = 0;int[] next = nextArray(s2, m);while (x < n && y < m) {if (s1[x] == s2[y]) {x++;y++;} else if (y == 0) {x++;} else {y = next[y];}}return y == m ? x - y : -1;}public int[] nextArray(char[] s, int m) {if(m == 1) {return new int[]{-1};}int[] next = new int[m];next[0] = -1;next[1] = 0;int i = 2, cn = 0;while(i < m) {if(s[i - 1] == s[cn]) {next[i++] = ++cn;} else if(cn > 0) {cn = next[cn];} else {next[i++] = 0;}}return next;}
}