研究了一下KMP的字符串匹配算法，其核心思想与朴素匹配算法的区别主要就在于：主串的index指针不回溯。

而子串的指针j只回到next[j]的位置。

注意：KMP算法只有在主串与子串存在比较多的部分匹配，才能显出其性能优势。

以下是算法实现。

KMP：

package aray.Test;public class KMP {	static int count=0;	static int next[] = new int[100];	public static void getNext(String sub) {		int i = 1, j = 0;		next[1] = 0;		char[] T = sub.toCharArray();		while (i < T.length) {			if (j == 0 || T[i] == T[j]) {				i++;				j++;				next[i] = j;			} else {				j = next[j];			}		}	}	public static int index(String pri, String sub) {		int i = 0, j = 0;		char[] P = pri.toCharArray();		char[] S = sub.toCharArray();        getNext(sub);		while (i < P.length && j < S.length) {						if (j == 0 || P[i] == S[j]) {				i++;				j++;			} else {				j = next[j];			}						count++;		}		if (j >= S.length) {			return i - j;		} else			return 0;	}	public static void main(String[] args) {		String str = "adcsadcsadcsadcsadcsadafa";		String sub = "csada";        System.out.println(index(str,sub));        System.out.println("the total count of compare is:  "+count);         	}}

朴素匹配：

package aray.Test;public class PuShu {	static int count=0;		public static int index(String pri, String sub) {		int i =0, j = 0;		char[] P = pri.toCharArray();		char[] S = sub.toCharArray();		while (i < P.length && j < S.length) {						if (P[i] == S[j]) {				i++;				j++;			} else {				i=i-j+1;				j=0;			}						count++;		}		if (j >= S.length) {			return i - j;		} else			return 0;	}			public static void main(String[] args) {		String str = "adcsadcsadcsadcsadcsadafa";		String sub = "csada";        System.out.println(index(str,sub));        System.out.println("the total count of compare is:  "+count);         	}}