导航
导航

字符串匹配算法之KMP算法

2015.04.09 尤淇  热度 ℃

KMP Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * kmp算法实现
 * @param text 目标串
 * @param pattern 模式串
 * @return 返回模式串在目标串中的起始位置，不存在返回-1
 */
public int kmpSearch(String text, String pattern) {
	int i = 0;
	int j = 0;

	int textLen = text.length();
	int patternLen = pattern.length();

	int[] next = new int[patternLen];

	buildNext(pattern, next);

	while (i < textLen && j < patternLen) {
		if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
			i++;
			j++;
		} else {
			j = next[j];
		}
	}
	if (j == patternLen)
		return i - j;
	else
		return -1;
}

private void buildNext(String pattern, int[] next) {
	int patternLen = pattern.length();
	next[0] = -1;
	int k = -1;
	int j = 0;
	
	while (j < patternLen - 1) {
		if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
			++j;
			++k;
			if (pattern.charAt(j) != pattern.charAt(k))
				next[j] = k;
			else
				next[j] = next[k];
		} else {
			k = next[k];
		}
	}
}