上代码:
next道理懂了,运行过程还是没琢磨明白。
第二个next是优化的算法,还没看懂。
package com.test; public class Test { /** * kmp算法,主串指针不回溯的一种算法。时间复杂度可以达到O(n+m)nm是串长度 * 关键是要解决:当匹配到模式串的某个字符,发生不匹配之后;主串指针如何向右移动。(next就是解决这个问题) * next返回的是: * 1数组的意义: * 每个元素代表模式串一个字符,表示当这个字符失配,而前面的字符都匹配时,“主串当前指针要和模式串中的第几个字符继续比较”。 * 2这个结果数组的计算方式是: * 找到模式串当前这个字符紧挨着它前面的连续几个字符和模式串开头连续几个字符是否相等, * (1)没有匹配记录0, * (2)有匹配记录开头连续几个字符的个数(或者这个连续串的下个下标)。 * (3)-1代表母串指针需要移动 * @author yfchenlei * @date 2012-9-20 * @param str 主串 * @param sub 子串 * @param pos 主串开始位置 * @return */ public static int kmpIndexOf(String str, String sub, int pos){ int i = pos; int j = 0; int[] next = next2(sub); while(i < str.length() && j < sub.length()){ if(j == -1 || str.charAt(i) == sub.charAt(j)){ i++; j++; }else{ j = next[j]; } } if(j == sub.length()){ return i - sub.length(); } return -1; } /** * next算法 * @param sub 模式串 * @return */ public static int[] next1(String sub){ int len= sub.length(); int[] next = new int[len]; int i = 0; int j = 0; while(i < len){ next[i] = j -1; if(j == 0 || sub.charAt(i) != sub.charAt(j - 1)) j = 0; i++; j++; } return next; } /** * 优化next算法 * @param sub 模式串 * @return */ public static int[] next2(String sub){ int[] next = new int[sub.length()]; next[0] = -1; int i = 0; int j = -1; while (i < sub.length() - 1) { if (j == -1 || sub.charAt(i) == sub.charAt(j)) { i++; j++; if (sub.charAt(i) != sub.charAt(j)) { next[i] = j; } else { next[i] = next[j]; } } else { j = next[j]; } } return next; } public static void main(String[] args) { } }
。
相关推荐
模式匹配的kmp算法,可大大提高效率,时间复杂度仅为O(n*M),对于初学数据结构的有一定的帮助
字符串模式匹配KMP实验 字符串模式匹配KMP实验
串的模式匹配的C语言实现,同时,还会有完好的界面,使用户输入的数据KMP实现与传统实现两种结果进行对比,完全能通过。
《数据结构》串章节字符串的模式匹配KMP算法详解
《字符串模式匹配KMP算法》教学课例设计[归纳].pdf
采用C语言实现模式匹配KMP算法源代码,自己亲自写的,绝对可用。
模式匹配KMP算法C代码
字符串模式匹配KMP算法PPT学习教案.pptx
KMP字符串模式匹配算法ppt,KMP算法是很精妙的算法,同时比较难懂。KMP字符串模式匹配算法ppt
LZ77算法与模式匹配KMP算法的结合及算法实现.doc
KMP 字符串模式匹配详解 KMP算法是对传统模式匹配算法的较大改进,在传统的模式匹配算法中,当出现主串中的字符与子串中的字符不等时,同时向前回溯了两个指针,一个是主串的指针,一个是子串的指针。而KMP算法的...
这是个比较难理解的算法,虽然代码就那么几行,但真正理解清楚还是要会时间的。
kmp算法ppt,代码是pascal的,信息学奥赛的同学可以看看哦
模式匹配的KMP算法 模式匹配的KMP算法 模式匹配的KMP算法 模式匹配的KMP算法
KMP字符串模式匹配算法,内是ppt讲解,比较通俗易懂了。。
理解模式匹配的含义,掌握简单匹配算法及模式匹配KMP算法 思想,实现(1)编程动态实现简单模式匹配算法及模式匹配KMP算(2)根据给定的主串与模式串,给出根据两种匹配算法进行匹配的各趟匹配结果; 应用例子: ...
严蔚敏版数据结构中的KMP算法的C++语言实现,有结果截图
字符串的模式匹配算法——KMP的C++实现。
《数据结构》用C语言实现的模式匹配KMP算法,可用于求出子串在主串中的位置。
我以前一直理解不上去KMP算法(说心里话,我有点笨),当我看到这篇文章时,我理解了,这篇文章不错,说得挺细的,而且还免费,下了看看