编辑代码

class Main {
	public static void main(String[] args) {
        //JSRUN引擎2.0，支持多达30种语言在线运行，全仿真在线交互输入输出。
        String t = "abcabca";
        String s = "aaabbbcdabcasd";
        System.out.println(kmp(s,t));
		System.out.println("Hello world!   - java.jsrun.net ");
	}
    public static int[] getNext(String t)
    {
        int[] next = new int[t.length()];
        int suffix = 0;
        int prefix = -1;
        next[0] = -1;
        while(suffix<t.length()-1)
        {
            if(prefix==-1||t.charAt(prefix)==t.charAt(suffix))
            {
                prefix++;
                suffix++;
                next[suffix] = prefix;
            }
            else
            {
                prefix = next[prefix];
            }
        }
        return next;
    }
    public static int kmp(String s,String t)
    {
        int i = 0;
        int j = 0;
        int[] next = getNext(t);
        while(i<s.length()-1&&j<s.length()-1)
        {
            if(j==-1||s.charAt(i)==t.charAt(j))
            {
                i++;
                j++;
            }
            else
            {
                j = next[j];
            }
        }
        if(j == t.length()-1)
        {
            return i-j;
        }
        else
        {
            return -1;
        }
    }
}