子字符串查找----KMP算法
Kunth-Morris-Pratt算法的基本思想是：当出现不匹配时，就能知晓一部分内容（因为匹配失败之前的字符已经和模式相匹配）。可以利用这些信息避免指针回退。令人惊讶的是，KMP算法在匹配失败时，总能将j设置为一个值以使i不回退。
在KMP算法中，不会回退文本指针i，而是用一个数组dfa[][]来记录匹配失败时指针j应该回退多远。对于每一个字符c，在比较了c和pat.charAt(j)后，dfa[c][j]表示的是应该和下一个文本字符比较的模式字符的位置。在匹配时会继续比较下一个字符，因此dfa[pat.charAt(j)][i]总是j+1; 在不匹配时，不仅可以知道txt.charAt(i)的字符，还可以知道正文中前j-1个字符--它们就是模式中的前j-1个字符。
该过程可以使用有穷状态自动机说明，dfa[][]数组定义的就是一个有穷状态自动机。DFA的构造代码如下：
dfa[pat.charAt(0)][0] = 1;
for (int x = 0, j = 1; j < m; j++) {
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][x];
dfa[pat.charAt(j)][j] = j+1;
x = dfa[pat.charAt(j)][x];
} 下面代码的实现在构造函数中根据模式字符串构造了一个DFA，使用search()方法在文本中查找字符串。
public class KMP {
private final int R;
private int[][] dfa;
private String pat;
public KMP(String pat) {
this.R = 256;
this.pat = pat;
int m = pat.length();
dfa = new int[R][m];
dfa[pat.charAt(0)][0] = 1;
for (int x = 0, j = 1; j < m; j++) {
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][x];
dfa[pat.charAt(j)][j] = j+1;
x = dfa[pat.charAt(j)][x];
}
}
public int search(String txt) {
int m = pat.length();
int n = txt.length();
int i, j;
for (i = 0, j = 0; i < n && j < m; i++) {
j = dfa[txt.charAt(i)][j];
}
if (j == m) return i - m;
return n;
}
}对于长度为M的模式字符串和长度为N的文本，KMP子字符串查找算法访问的字符串不会超过M+N个。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.01.26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读