题目描述
思路:典型的数据结构中的KMP算法实现
代码与解析
假设两个字符串长度分别为m和n,暴力解则为O(m*n)
引入KMP算法降低时间复杂度,求next数组是O(m) 遍历匹配串是O(n)
KMP关键思路
①求出模式串的next数组,即最长公共前后缀的长度。前缀定义,不含最后一个字母,后缀定义不含第一个字母。
next[i] 代表第i个位置的最长公共前后缀的长度
这里定义next[0]=0,即第一个字母的最长公共前后缀长度都是0
遍历模式串
j代表模式串中i位置的最长前后缀长度为j,所以不配的时候回退为next[j-1]
private static void getNext(int[] next, String s) {int j = 0;next[0] = 0;for (int i = 1; i < s.length(); i++) {while (j > 0 && s.charAt(j) != s.charAt(i))j = next[j - 1];if (s.charAt(j) == s.charAt(i))j++;next[i] = j;}}
模式串与匹配串
public static int strStr(String haystack, String needle) {if (needle.isEmpty()) return 0;int[] next = new int[needle.length()];getNext(next, needle);int j = 0;for (int i = 0; i < haystack.length(); i++) {while (j > 0 && needle.charAt(j) != haystack.charAt(i))j = next[j - 1];if (needle.charAt(j) == haystack.charAt(i))j++;if (j == needle.length())return i - needle.length() + 1;}return -1;
}
整体KMP代码
class Solution {public int strStr(String haystack, String needle) {if (needle.isEmpty())return 0;// 字符串的模式匹配int length = needle.length();int[] next = new int[length];getNext(next, needle);// System.out.println(Arrays.toString(next));int j = 0;// j 来对子串操作 i来操作匹配串for (int i = 0; i < haystack.length(); i++) {while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {j = next[j - 1];}if (haystack.charAt(i) == needle.charAt(j)) {j++;}//模式串到头了,j应该是最后一个字符之后又加一了,所以j==length,而不是length-1if(j == length){return i-length+1;}}return -1;}// 构建next数组,用kmp算法实现此功能private void getNext(int[] next, String needle) {int j = 0;// 最长相等前后缀长度 不算第一个和最后一个字母,所以对于第一个位置,公共长度是0next[0] = j;for (int i = 1; i < next.length; i++) {while (j > 0 && needle.charAt(i) != needle.charAt(j)) {// 其实这里比较的是i和j都向公共前后缀子串后移动了一个之后的位置// 不相等,回退 j是公共长度,所以应该回退到 next[j-1] 这个之前的是可能相交的公共子串部分j = next[j - 1];}if (needle.charAt(i) == needle.charAt(j)) {j++;}next[i] = j;}}
}