kmp java实现,KMP算法的实现

　　00-1010图解代码实现

　　其实就是看当前好的前缀和后缀是否匹配，找到最长匹配长度，直接滑动。鉴于不止一次寻找最长匹配长度，我们可以先完全初始化一个数组，在当前情况下保存好前缀。最长匹配长度是多少？这个时候我们的下一个数组就出来了。

　　我们定义了一个next数组，表示当前好前缀下一个好前缀的前缀和后缀的最长匹配子串长度。这个最长的匹配长度表示这个子串之前已经匹配过了，所以不需要再次匹配，直接从子串的下一个字符开始匹配。

　　每次计算next[i]时是否需要匹配每一个字符，是否可以从next[i-1]推导，减少不必要的比较。

　　有了这个想法，我们来看看下面的步骤：

　　假设next[I-1]=k-1；

　　如果modelStr[k]=modelStr[i]，那么next[i]=k

　　If modelStr[k]！=modelStr[i]，能否直接确定下一个[i]=下一个[i-1]？

　　通过上面的例子，我们可以清楚的看到，下一个[我]！=next[i-1]，那么当modelStr[k]！=modelStr[i]，我们知道下一个[0]，下一个[1]…下一个[i-1]。如何才能击倒下一个[我]？

　　假设modelStr[x…i]是前缀和后缀能匹配的最长后缀子串，那么最长匹配的前缀子串就是modelStr[0…i-x]

　　当我们找到这个最长匹配串的时候，他前面的下一个最长匹配串(不包括当前的I)，也就是modelStr[x…i-1]，应该是之前已经求解过的，那么我们只需要找到这个已经求解过的，假设前缀子串是modelStr[0…i-x-1]，后缀子串是modelStr[x…i-1]。而modelStr[i-x]==modelStr[i]，这个前缀后缀子串是次前缀子串，当前字符是最长匹配的前缀后缀子串。

　　00-1010首先在kmp算法中，最重要的next数组，这个数组标记了最长前缀后缀匹配子串到当前下标的字符数。在kmp算法中，如果一个前缀是好前缀，也就是匹配模式串前缀，我们可以使用一定的技巧向前滑动多个字符。详见前面的解释。我们事先不知道哪些前缀好，匹配过程不止一次，所以一开始就调用一个初始化方法来初始化下一个数组。

　　1.如果前一个字符的最长前缀子串的下一个字符==当前字符，则前一个字符的最长前缀子串可以直接与当前字符相加。

　　2.如果不是，需要找出之前存在的最长前缀子串的下一个字符等于当前子串，然后设置当前字符子串的最长前缀后缀子串。

　　int[]next；/* * *初始化下一个数组* @ param modelStr */public void init(char[]modelStr){//先计算下一个数组//遍历modelStr，遍历的字符和前面的字符组成一个字符串next=new int[modelStr . length]；int start=0；while(start modelStr . length){ next[start]=this . recursion(start，modelStr)；开始；} }/* * * * @ param I The character * @ return */private int recursion(int I，char [] modelstr) {//next记录数字，而不是下标if (0==i) {

　　 return 0; } int last = next[i -1]; //没有匹配的,直接判断第一个是否匹配 if (0 == last) { if (modelStr[last] == modelStr[i]) { return 1; } return 0; } //如果last不为0，有值，可以作为最长匹配的前缀 if (modelStr[last] == modelStr[i]) { return next[i - 1] + 1; } //当next[i-1]对应的子串的下一个值与modelStr不匹配时，需要找到当前要找的最长匹配子串的次长子串 //依据就是次长子串对应的子串的下一个字符==modelStr[i]; int tempIndex = i; while (tempIndex > 0) { last = next[tempIndex - 1]; //找到第一个下一个字符是当前字符的匹配子串 if (modelStr[last] == modelStr[i]) { return last + 1; } -- tempIndex; } return 0; }然后开始利用next数组进行匹配，从第一个字符开始匹配进行匹配，找到第一个不匹配的字符，这时候之前的都是匹配的，接下来先判断是否已经是完全匹配，是直接返回，不是，判断是否第一个就不匹配，是直接往后面匹配。如果有好前缀，这时候就利用到了next数组，通过next数组知道当前可以从哪个开始匹配，之前的都不用进行匹配。

public int kmp(char[] mainStr, char[] modelStr) { //开始进行匹配 int i = 0, j = 0; while (i + modelStr.length <= mainStr.length) { while (j < modelStr.length) { //找到第一个不匹配的位置 if (modelStr[j] != mainStr[i]) { break; } ++ i; ++ j; } if (j == modelStr.length) { //证明完全匹配 return i - j; } //走到这里找到的是第一个不匹配的位置 if (j == 0) { ++ i; continue; } //从好前缀后一个匹配 j = next[j - 1]; } return -1; }

到此这篇关于详解Java中KMP算法的图解与实现的文章就介绍到这了,更多相关Java KMP算法内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

kmp java实现,KMP算法的实现

目录

相关文章阅读