アルゴリズム_KMP_文字列のサブストリングの数

public class KMP {

	public static void main(String[] args) {

		String source = "abccdfabvsfnabc";
		String dest = "ab";
		int[] next = kmpNext(dest);
		System.out.println(kmp(source, dest, next));
	}

	/**
	 * kmp        
	 * @param source
	 * @param dest
	 * @param next
	 * @return
	 */
	public static int kmp(String source, String dest, int[] next) {
		int count = 0;
		for (int i = 0, j = 0; i < source.length(); i++) {
			while (j > 0 && source.charAt(i) != dest.charAt(j)) {
				j = next[j - 1];
			}
			if (source.charAt(i) == dest.charAt(j)) {
				j++;
			}
			if (j == dest.length()) {
				count++;
				j = 0;
			}
		}
		return count;
	}

	/**
	 *         ，              kmp  
	 * @param dest
	 * @return
	 */
	private static int[] kmpNext(String dest) {
		int[] next = new int[dest.length()];
		next[0] = 0;
		for (int i = 1, j = 0; i < dest.length(); i++) {
			while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
				j = next[j - 1];
			}
			if (dest.charAt(i) == dest.charAt(j)) {
				j++;
			}
			next[i] = j;
		}
		return next;
	}
}

package t26;
//             
public class Test {
	public static void main(String[] args) {
		System.out.println(times("abccdfabvsfnabc","ab"));
	}
	
	public static int times(String str,String subStr) {
		int times=0;
		for(int i=0;i<str.length()-subStr.length()+1;i++) {
			if(str.startsWith(subStr, i)) {
				times++;
				i+=subStr.length()-1;
			}
		}
		return times;
	}
}