- 浏览: 130583 次
- 性别:
- 来自: ...
文章分类
最新评论
一直把精力放在web应用的开发和框架学习,应用,架构的领悟等等这些几乎见不到算法存在的场景中,对算法这个‘内功’修炼一直有种没处下牙的尴尬境地。不过这不代表从此不再接触算法,一味的只去掌握JDK封装好的API库。今天使用String的indexOf(...)的时候突然想看看这个方法的实现,于是...
1.6.0.17的算法实现主要代码:
这个算法还是使用了简单匹配,首先找到第一个匹配的字符,然后在当前之后创建新的指针指向第二个字符,然后匹配剩余的。这个算法其实相当于i指针在匹配到不相等的时候回缩指针。所以时间复杂度是两串长度之积。不知是不是觉得不会有较长的字符串的匹配,所以不去优化,还是我把算法理解错了,呵呵。
既然我觉得这个算法不怎么好,对于较长字符串的匹配效率不怎么样,那就不得不看数据结构中被大加赞赏的KMP模式匹配算法了。具体的算法原理就不弄斧了,优秀的牛人们早就在网上留下了过分多的优秀讲解。我这里把我理解原理后的Java实现代码分享一下:
再有就是一个简单的test case.
算法这门功夫是一个程序员维持程序生命的根源或者说内功,虽然对我来说,练就基本功都需要很大的精力,我想我还是会在日常的工作学习中勤加练习的。
1.6.0.17的算法实现主要代码:
for (int i = sourceOffset + fromIndex; i <= max; i++) { /* Look for first character. */ if (source[i] != first) { while (++i <= max && source[i] != first); } /* Found first character, now look at the rest of v2 */ if (i <= max) { int j = i + 1; int end = j + targetCount - 1; for (int k = targetOffset + 1; j < end && source[j] == target[k]; j++, k++); if (j == end) { /* Found whole string. */ return i - sourceOffset; } } } return -1;
这个算法还是使用了简单匹配,首先找到第一个匹配的字符,然后在当前之后创建新的指针指向第二个字符,然后匹配剩余的。这个算法其实相当于i指针在匹配到不相等的时候回缩指针。所以时间复杂度是两串长度之积。不知是不是觉得不会有较长的字符串的匹配,所以不去优化,还是我把算法理解错了,呵呵。
既然我觉得这个算法不怎么好,对于较长字符串的匹配效率不怎么样,那就不得不看数据结构中被大加赞赏的KMP模式匹配算法了。具体的算法原理就不弄斧了,优秀的牛人们早就在网上留下了过分多的优秀讲解。我这里把我理解原理后的Java实现代码分享一下:
public class KmpTest { /**The Next() function of The KMP algorithm. * @param chars * @return */ private int[] createNext(char[] chars) { int len = chars.length; int[] nextArr = new int[len]; int i = 0, j = -1; while (i < len - 1) { if ((j == -1) || (chars[j] == chars[i])) { i++; j++; if (chars[j] != chars[i]) { nextArr[i] = j + 1; } else { nextArr[i] = nextArr[j]; } } else { j = nextArr[j] - 1; } } return nextArr; } /**The default method which can find the index of a pattern String in a specific String. * Pattern from the first character of the specific String. * @param str * @param pattern * @return */ public int kmpIndex(String str, String pattern) { return kmpIndex(str, pattern, 0); } /**Pattern from a specific postion of the specific String. * @param str * @param pattern * @param pos * @return */ public int kmpIndex(String str, String pattern, int pos) { char[] strChars = str.toCharArray(); char[] ptenChars = pattern.toCharArray(); int len = strChars.length; int[] next = createNext(ptenChars); int i = pos - 1, j = -1; while (i < len && j < next.length) { if ((j == -1) || (strChars[i] == ptenChars[j])) { i++; j++; } else { j = next[j] - 1; } } if (j > next.length - 1) { return i - next.length; } else { return -1; } } }
再有就是一个简单的test case.
import junit.framework.Assert; import junit.framework.TestCase; public class KmpTestCase extends TestCase { KmpTest kmpTest; @Override protected void setUp() throws Exception { kmpTest = new KmpTest(); } public void testKmpIndex() { Assert.assertEquals(0, kmpTest.kmpIndex("ababaababc", "ababa")); Assert.assertEquals(2, kmpTest.kmpIndex("ababaababc", "abaab")); Assert.assertEquals(6, kmpTest.kmpIndex("ababaababc", "babc")); Assert.assertEquals(-1, kmpTest.kmpIndex("ababaababc", "baabc")); Assert.assertEquals(2, kmpTest.kmpIndex("ababaababc", "abaa", 2)); Assert.assertEquals(-1, kmpTest.kmpIndex("ababaababc", "abaa", 3)); } }
算法这门功夫是一个程序员维持程序生命的根源或者说内功,虽然对我来说,练就基本功都需要很大的精力,我想我还是会在日常的工作学习中勤加练习的。
发表评论
文章已被作者锁定,不允许评论。
-
一道位操作的趣味编程题
2010-03-14 10:50 2084看到一道很有意思的编程题:大厅里有64盏灯,每盏灯都编 ... -
一道字符串截取的编程题
2010-03-11 10:52 2276最近接触到一道字符串截取的编程题:编写一个截取字符串的 ... -
一道多线程趣味热身题
2010-02-28 18:01 1915保持对知识点或者技术的熟悉度对于程序员至关重要,要学会 ... -
疑似Google多线程面试题的Java实现
2010-02-24 17:39 4907来到一个完全陌生的地方,即将一切从新开始,内心兴奋又忐 ... -
Mina的线程池实现分析(2)
2010-02-10 17:31 4522分析了I/O事件的存储,下面看看多个Worker同时工 ... -
Mina的线程池实现分析(1)
2010-02-10 17:28 11575线程池是并发应用中,为了减少每个任务调用的开销增强性能 ... -
多线程基础总结十一--ConcurrentLinkedQueue
2010-02-03 17:52 12840ConcurrentLinkedQueue充分使用了a ... -
LinkedBlockingQueue应用--生产消费模型简单实现
2010-01-29 20:45 8137之前介绍时LinkedBlockingQueue提到了 ... -
多线程基础总结十--LinkedBlockingQueue
2010-01-28 14:33 15372随着多线程基础总结的增多,却明显的感觉知道的越来越少, ... -
号称放倒一片的一道J2SE基础题的个人理解
2010-01-23 14:07 2793近日无意中看到一道Java基础题,号称在接受测试的10 ... -
多线程基础总结九--Mina窥探(1)
2010-01-21 23:46 5401一直以来的多线程的基础总结都是脱离应用的,但是要说多线 ... -
多线程基础总结八--ReentrantReadWriteLock
2010-01-15 23:22 7510说到ReentrantReadWriteLock,首先 ... -
多线程基础总结七--ReentrantLock
2010-01-09 23:17 7678之前总结了部分无锁机制的多线程基础,理想的状态当然是利 ... -
关于atomic问题的一点理解
2009-12-30 16:42 2440之前看到一个帖子是关于atomic使用的,当时没有仔细 ... -
多线程基础总结六--synchronized(2)
2009-12-18 18:45 1869早在总结一时,我就尽量的把synchronized的重点 ... -
多线程基础总结五--atomic
2009-12-17 19:46 3550在简单介绍java.util.c ... -
多线程基础总结四--ThreadLocal
2009-12-16 19:48 2719说到ThreadLocal,首先 ... -
多线程基础总结三--volatile
2009-12-15 20:09 2525前面的两篇总结简 ... -
多线程基础总结二--Thread
2009-12-12 23:27 2668对于Thread来说 ... -
多线程基础总结一--synchronized(1)
2009-12-12 23:23 3068最近写关于并发的小应 ...
相关推荐
KMP算法的实现, 这程序代码是基于KMP算法来实现的,虽然很简单,但是可能也会对你有帮助的
模式匹配中的KMP算法的c语言实现及简单的应用介绍!
简单的kmp算法实现,代码结构十分清晰,适合初学者理解kmp算法
最近在学习数据结构,将KMP算法用C#简单实现了下
KMP算法的c++实现,根据一篇讲解kmp算法的文档写的,带工程可编译,可以直接作为项目代码使用,也可以作为学习使用,实现简单、灵活
kmp算法 KMP算法的简单实现示例
KMP算法的介绍以及实现,简单的介绍会让你更容易弄懂KMP算法的过程
KMP算法简单实现,用于字符串模式匹配算法
具体实现上,KMP算法使用一个next()函数,该函数包含模式串的局部匹配信息。在匹配失败时,next()函数用来确定模式串的最左可能有效匹配位置,而非简单地将模式串重新从左向右扫描。这样大大减少了不必要的匹配次数...
java实现KMP算法,代码非常简单,容易理解。
kmp算法的简单实现,应该对理解算法比较有帮助
带有简单示例,亲测可用!!! 函数组成: public static void main(String[] args) private int search(String str, String pat) public static int[] generateNext(String dest)
实现KMP算法,简单易懂,由学生实验实现,对于ACM学习有很大帮助。
这是一类比较实用的小系统,实现了从文件中读出的内容进行查找与替换
KMP(Knuth-Morris-Pratt)...总体来说,KMP算法相对于简单的暴力匹配算法具有更高的效率和更好的性能,适用于大规模文本和模式匹配的场景。 以下是使用C语言实现KMP算法的示例代码: ```c #include #include void c
kmp算法 kmp算法用于字符串的模式匹配,也就是找到模式字符串在目标字符串的第一次出现的位置 比如 abababc 那么bab在其位置1处,bc在其位置5处 我们首先想到的最简单的办法就是蛮力的一个字符一个字符的匹配,...
主要介绍了C语言kmp算法简单示例和实现原理探究,本文用简洁的语言说明KMP算法的原理,并给出了示例,需要的朋友可以参考下
字符串模式匹配算法 sunday算法实现。说到字符串匹配算法,立马就想到了KMP算法,谁让KMP这么经典呢,各种算法教材里必然有KMP啊。但是KMP算法太复杂了,比KMP更简单更高效的算法就是Sunday算法。
给定一个文本,在该文本中查找并定位任意给定字符串 实现BF算法; 实现BF算法的改进算法:KMP算法和BM算法; 对上述三个算法进行时间复杂性分析,并设计时间程序验证分析结果。
c代码-简单实现kmp算法