KMP算法的java实现

简单的KMP，说实话我觉得大多数讲KMP算法的都不会KMP算法。。

public class Solution {
public int isContains(String s1, String s2) {

int[] next = getNext(s2);

for(int i = 0; i < s2.length(); ++i) {
            System.out.print(next[i] + " " );
        }

        System.out.println();

int i = 0;
int j = 0;
while (i < s1.length() && j < s2.length()) {
if(j == -1 || s1.charAt(i) == s2.charAt(j)) {
                ++i;
                ++j;
            } else {
//++i;
                j = next[j];
            }

            System.out.println("j" + " " + j);
        }
if(j == s2.length()) return (i-j);
else return -1;
    }

public int[] getNext(String subString) {
int[] next = new int[subString.length()+5];
        next[0] = -1;
int k = -1;
int j = 0;
while (j < subString.length() -1) {
if(k==-1 || subString.charAt(k) == subString.charAt(j)) {
                ++k;
                ++j;
                next[j] =k;
            } else {
                k = next[k];
            }
        }
return next;
    }

public static void main(String[] args) {
        String s1 = new String("abab");
        String s2 = new String("cbca");

        Solution solution = new Solution();
        System.out.println(solution.isContains(s1, s2));
    }
}