本文共 1519 字，大约阅读时间需要 5 分钟。

求next数组

private int[] kmpNext(String str){
           int[]  next = new int[str.length()];        int j = 0;        for(int i = 1; i < str.length(); i++){
               while(j > 0 && str.charAt(i) != str.charAt(j)){
                   j = next[j-1];            }            if(str.charAt(i) == str.charAt(j)){
                   j++;            }            next[i] = j;        }        return next;    }

整体思路： 基于leetcode 28

class Solution {
       private int[] next; // next数组    public int strStr(String haystack, String needle) {
           if (needle==null||haystack==null||needle.length()<=0) {
   			return 0;		}        next = kmpNext(needle);        int m = haystack.length();        int n = needle.length();                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-j+1;            }        }                return -1;            }        private int[] kmpNext(String str){
           int[]  next = new int[str.length()];        int j = 0;        for(int i = 1; i < str.length(); i++){
               while(j > 0 && str.charAt(i) != str.charAt(j)){
                   j = next[j-1];            }            if(str.charAt(i) == str.charAt(j)){
                   j++;            }            next[i] = j;        }        return next;    }}

转载地址：http://lbvgz.baihongyu.com/