KMP算法是由三个人共同提出,并以他们名字的首字母命名的,故叫做KMP算法。该算法相对于 Brute-Force(暴力)算法有比较大的改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。
KMP算法要利用一个next数组:next[i]:从下标为0到i的子串的前缀和后缀相等的最大长度。同时也就表示要回退的位置(不是对称,是从左往右相等)
前缀:不包含最后一个字符的子串。比如aab的前缀是a或者aa
后缀:不包含第一个字符的子串。比如aab的后缀是b或者ab
求出next数组后,每次遇到不相等的字符,就去找它next数组中对应的前一个下标中的值,这个值就是要回退的位置(循环)
比如aaccaa所对应的next数组的值为0,1,0,0,1,2。
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回 -1 。
输入:haystack = “hello”, needle = “ll”
输出:2
输入:haystack = “aaaaa”, needle = “bba”
输出:-1
public int strStr(String haystack, String needle) { // haystack为匹配串,needle为模式串 int n=needle.length(); int m=haystack.length(); if (n==0) return 0; // next[i]:表示要回溯的位置 int[] next = new int[n]; next[0]=0; // 求next数组(固定的方法) for (int i = 1,j=0; i < n; i++) { // 不相等 while (j>0&&needle.charAt(j)!=needle.charAt(i)){ j=next[j-1]; } // 相等 if (needle.charAt(j)==needle.charAt(i)){ j++; next[i]=j; } } // 开始判断模式串的位置,如果j==模式串的长度就说明匹配成功了 for (int i = 0,j=0; i < m; i++) { while (j>0&&haystack.charAt(i)!=needle.charAt(j)){ j=next[j-1]; } if (haystack.charAt(i)==needle.charAt(j)) j++; if (j==n) return i-n+1; } return -1; }