解题思路:
KMP算法
需要先求得最长相等前后缀,并记录在next数组中,也就是前缀表,前缀表是用来回退的,它记录了模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配。
next[ j - 1 ] 记录了 j 要回退的位置(注意要限制 j > 0 )
最长相等前后缀的例子如下:
a 0
aa 1
aab 0
aaba 1
aabaa 2
aabaaf 0
KMP算法的应用,例如:
要在文本串:aabaabaaf 中查找是否出现过一个模式串:aabaaf。
第一次匹配aabaaf时,aabaa成功,到f时失败
根据回退
aabaa的最长相等前后缀为2
即 j 回到下标为2的位置,也就是b
第二次匹配时,即为aabaabaaf 中的baaf开始匹配
(因为匹配到的串文本串和模式串是前后对称的,即aabaa和aabaa,aabaa的尾和aabaa的头中的aa可以续接上,所以不用再从aa开始了,aa已经匹配到了,直接从b开始)
匹配成功
class Solution {public int strStr(String haystack, String needle) {int[] next = new int[needle.length()];getNext(next, needle);int j = 0;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++;if (j == needle.length()) return i - needle.length() + 1;}return -1;}public void getNext(int[] next, String needle) {int j = 0;next[0] = 0;for (int i = 1; i < needle.length(); i++) {while (j > 0 && needle.charAt(i) != needle.charAt(j)) j = next[j - 1];if (needle.charAt(i) == needle.charAt(j)) j++;next[i] = j;}}
}