KMP算法实现代码
发布时间：2020-12-16 07:47:46 所属栏目：百科 来源：网络整理
导读：今天PHP站长网 52php.cn把收集自互联网的代码分享给大家，仅供参考。 KMP算法 算法思想 相比蛮力算法，KMP算法预先计算出了一个哈希表，用来指导在匹配过程中匹配失败后尝试下次匹配的起始位置，以此避免重复的读入和匹配
|
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家，仅供参考 KMP算法算法思想相比蛮力算法，KMP算法预先计算出了一个哈希表，用来指导在匹配过程中匹配失败后尝试下次匹配的起始位置，以此避免重复的读入和匹配过程。这个哈希表被叫做“部分匹配值表(**Particial match table**)”，它的设计是算法精妙之处。部分匹配值表 要理解部分匹配值表，就得先了解字符串的前缀(prefix)和后缀(postfix)。
还是针对字符串ABCAB，它的部分匹配值表为：
前缀:除字符串最后一个字符以外的所有头部串的组合。 后缀：除字符串第一个字符以外的所有尾部串的组合。 部分匹配值：一个字符串的前缀和后缀中最长共有元素的长度。 举例说明：字符串ABCAB 前缀：{A， AB， ABC， ABCA} 后缀：{BCAB， CAB， AB， B} 部分匹配值：2 （AB） 而所谓的部分匹配值表，则为模式串的所有前缀以及其本身的部分匹配值。 A B C A B
0 0 0 1 2
算法代码 public static int[] next;
public static boolean kmp(String str,String dest) {
for (int i = 0,j = 0; i < str.length(); i ++) {
while (j > 0 && str.charAt(i) != dest.charAt(j))//iterate to find out the right next position
j = next[j - 1];
if (str.charAt(i) == dest.charAt(j))
j ++;
if (j == dest.length())
return true;
}
return false;
}
public static int[] kmpNext(String str) {
int[] next = new int[str.length()];
next[0] = 0;
for (int i = 1,j = 0; i < str.length(); i ++) {//j == 0 means the cursor points to nothing.
//the j here stands for the number of same characters for postfix and prefix,instead of
//the index of the end of prefix.
while (j > 0 && strt.charAt(j) != sr.charAt(i))
j = next[j - 1]; //watch out here! it's j - 1 here,instead of j
if (str.charAt(i) == str.charAt(j))
j ++;
next[i] = j;
}
return next;
}
参考博文：
KMP算法-中文参考博文和
KMP算法-英文参考博文
以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |