KMP子字符串查找算法
KMP子字符串查找算法
概述
算法的基本思想是：当出现不匹配时，就能知晓一部分文本的内容，可以利用这些信息避免将指针回退到所有这些已知的字符串之前。
DFA（确定有限状态机）模拟
提前判断如何重新查找，而这种判断只取决于模式本身，所以可以对模式的字符序列做一个确定有限状态机。
DFA的数据结构表示为二维数组dfa[R][M]，其中R为指定字典中的字符集的个数（比如ASCII为256），M为匹配字符串pat的长度，状态的意思是文本中某个位置i匹配pat的程度，0状态为未匹配状态，M状态为终止状态，找到了完整匹配的字符串。 如图中R=3，M=6，二维数组中的值指向下一个状态。
构造DFA
穷举模式pat的所有可能情况，将这些情况用状态图表示。其中X记录匹配失败时重启的索引位置。
编码实现
用暴力算法实现子字符串查找算法
public int search(String txt, String pat) {
int i, N = txt.length();
int j, M = pat.length();
for (i = 0, j = 0; i < N && j < M; i++) {
if (txt.charAt(i) == pat.charAt(j)) {
j++;
} else { //显式回退
i-=j;
j=0;
}
}
if (j==M) return i-M;
return N;
}KMP查找
/**
* @return pat在txt中开始出现的位置，如果等于txt.length()表示没有找到
*/
public int search(String txt) {
int M = pat.length();
int N = txt.length();
int i, j; //i指向txt，j指向pat
for (i = 0, j = 0; i < N && j < M; i++) {
j = dfa[txt.charAt(i)][j];
}
if (j == M) return i - M; //匹配
return N; //不匹配
}构造DFA
private final int R; // the radix
private int[][] dfa; // the KMP automoton
private String pat;
public KMP(String pat) {
this.R = 256; //设置字典大小
this.pat = pat;
//构造pat对应的dfa
int M = pat.length();
dfa = new int[R][M];
dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++) { //X记录匹配失败时的索引位置,j指向pat
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]; //更新重启位置X
}
}优缺点
优点：适合在长度不确定的输入流中进行查找，不需要在输入中回退。
缺点：最坏的情况（在重复性很高的文本中查找重复性很高的模式）在实际应用中很少出现，还不如使用暴力算法来的容易，性能也差不了多少。参考
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年05月02日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录