KMP算法用于字符串匹配

关于next数组的解释参见：

KMP算法比较详尽的一个解释见 

KMP算法详解——适合初学KMP算法的朋友

：

改写java版本如下：

import java.util.Arrays;public class KMPtest {	public static int[] getNextArray(String s) {		char[] target = s.toCharArray();		int size = target.length;		int[] next = new int[size + 1];		next[0] = 0;		next[1] = 0;		int k = 0;// /* 第i次迭代开始之前，k表示next[i-1]的值 */		for (int i = 2; i < size + 1; i++) {			for (; k != 0 && target[k] != target[i - 1]; k = next[k]) {			}			if (target[k] == target[i - 1]) {				k++;			}			next[i] = k;		}		return next;	}	public static void kmpmatch(String text, String pattern) {		int m, n, s, q;		int[] next = getNextArray(pattern);		char[] textarray = text.toCharArray();		char[] patternarray = pattern.toCharArray();		m = patternarray.length;		n = textarray.length;		q = s = 0; // q表示上一次迭代匹配了多少个字符， s表示这次迭代从text的哪个字符开始比较		while (s < n) {			for (q = next[q]; q < m && patternarray[q] == textarray[s]; q++, s++) {			}			if (q == 0) {				s++;			} else if (q == m) {				System.out.println("matched success at " + (s - m));			}		}	}	public static void main(String[] args) {//		int[] next = getNextArray("abababca");//		System.out.println(Arrays.toString(next));		kmpmatch("bdcaccacaercacdcaca", "caca");	}}

运行结果：

matched success at 5

matched success at 15