题解 | #kmp算法#

本题： 相对于原生的改变，只有一处。

原生是匹配到了，直接返回模式串在文本串中的起使位置
而此题是找到了，ans++。然后让j回退。
就是 S = ababab T = abababab 

当第一次匹配结束
	此时的状态 S = [ababab]  T = [ababab]ab
    next[j-1] 为此时前后缀长度，也就是4. 
    就是 j 回退回 j = 4, abab(ab) 
    此时 S的前缀[(abab)ab] == T的后缀[ab(abab)]  
    也就是说前四个字符不需要再次匹配了，直接比较接下来的两个字符。

原生kmp

class Solution {
    void getNext(int[] next, String needle) {
        int j = 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;
        }
    }
    public 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 && 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;
    }
}

import java.util.*;


public class Solution {
   
    public int kmp (String S, String T) {
        // write code here
        int[] next = new int[S.length()];
        int j = 0;
        for(int i = 1; i < S.length(); i++) {
            while(j > 0 && S.charAt(j) != T.charAt(i)) {
                j = next[j - 1];
            } 
            if(S.charAt(j) == T.charAt(i)) {
                j++;
            }
            next[i] = j;
        }
        j = 0;
        int ans = 0;
        for(int i = 0; i < T.length(); i++) {
            while(j > 0 && S.charAt(j) != T.charAt(i)) {
                j = next[j - 1];
            } 
            if(S.charAt(j) == T.charAt(i)) {
                j++;
            }
            if(j == S.length()) {
                ans++;
                j = next[j - 1];
            }
        }
        return ans;
    }
}