KMP字符串匹配算法和JDK

一般的朴素字符串匹配算法: 从目标串Target的第一个字符开始扫描,逐一与模式串的对应字符进行匹配,若该组字符匹配,则检测下一组字符 如遇失配,则退回到Target的第二个字符,重复上述步骤,直到整个Pattern在Target中找到匹配,或者已经扫描完整个目标串也没能够完成匹配为止 算法理解起来很简单,实现起来也容易,但是其中包含了过多不必要的操作,也就是在目标串中,有些字符是可以直接跳过,不必检测的 但是在特定的情况下,这样的算法还是有可优化的地方的. 不妨假设我们的目标串:Target = “a b c d e a b c d e a b c d f” 需要匹配的模式串:Pattern = “c d f”; 那么当匹配到如下情况时: 因为e!=f,则进行下一次匹配 到最后可以看到: 这中间的四个字符d e a b 完全可以过跳进行检验,由此可见这个传统的方法还是有很多可以优化的地方的。 KMP算法的基本思想: 通过一个前缀函数进行贮存”有用信息”,下文称之为部分匹配值,一般使用next()函数进行描述 在失配后,并不简单地从目标串下一个字符开始新一轮的检测,而是依据在检测之前得到的有用信息,直接跳过不必要的检测,从而达到一个较高的检测效率。 这个函数能够反映出现失配情况时,系统应该跳过多少无用字符(也即模式串应该向右滑动多长距离)而进行下一次检测,在上例中,这个距离为4. 有效信息的求法 一个字符串除了最后一个字符,其余的字符的所有子集都是前缀 比如说 bread 的前缀为 b, br, bre, brea 一个字符串除了地一个字符,其余的所有子集均为后缀 比如说 bread 的后缀为 d, ad, ead,…

一切都是奖学金惹的祸

终于到了大三了,也想好好静下心来好好学习了,也要准备马上就要来的实习生面试笔试了。 同时,也到了评奖学金的时刻了。按理说,我的成绩也不错, 而且还有传说中的混奖学金大赛(蓝桥杯)的国三和省一,理论上应该是拿钱没有问题, 可是,不想我在大二上学期,一直特立独行,选了两门超修课,然后忘了= =,忘了。。。 于是,到期中考试我看课表的时候才发现有这两门课,于是乎- -,我就开始准备期末考试了,因为课程都不难,而且我都是有所了解的,所以看看书觉得应付考试也没什么问题,于是就放在一边了,到了离期末还有几周的时候,我去问学长,这两门课的期末考试内容,然后他们告诉我说,没有期末考试。。没有期末考试,。。。于是我这两门蛋疼的课都成了0分,虽然是很悲剧,但是也了了我的一个心愿,拿一次0分= =。。。 这件事就这么安静的过去了,然后,高潮来了,因为我们评定奖学金对学习是有硬性要求的,不能低于70的,但是超修课不算。所以我就放心的过了几周,到了15号(23号评定结束),辅导员找到我说,本来想分给我卓越创新一等奖学金的,但是我有两个0分。。不能给,在被禁名单里。。我瞬间就无语了,然后赶紧和她说明情况,然后她淡淡说了一句,我看看那能不能解决,于是打了几个电话之后给我指明了一条明路,去学院教务处开个证明,说明这是超修课,然后去校教务处看看能不能消除这两个0分,接着去团委盖个章,然后去找学工处,让他们消除这个0分限制。 我是我屁颠屁颠的去找了学院教务处,然后扯了半天,好不容易说服他给我开了个证明(说了15分钟,还不算辅导员找他的时间(辅导员失败了。。。))。。。然后,这一天就结束了。还不到5点,都下班了- -。 第二天,我终于拿着证明去了校教务处,和他们说明情况,然后他们看了下我的证明,淡淡的说了一句,删,是不可能的,到时候你可以申请隐藏成绩,出国的时候没有影响。。然后问道奖学金的事,他说了句,这个啊,就去找学工处就行了。然后我又去找了学工处,期间我走错楼的事情我也就不说了,终于我找到了已经快下班的学工处头头。。。然后说明情况,提交证明,然后,他很牛逼的用超管进了系统,然后删了这两门成绩,然后和我说,没问题,于是,我打电话给了辅导员,此时,他已经下班,然后说,明天我看看啊。于是,又一天过去了。 到了周三,辅导员说还是不行。。。于是我翘课(课下午全满,不翘这天就没时间了),去找学工处头头,然后,他不上班 – -,上午下午我都去了。。。都没上班。。。我了个擦,老师还点名- -,我是第一次不去啊。。。然后到了周四,他终于在了,我又去找了他,他又很牛逼的用超管进系统,有重复上述步骤,然后和我说,你和辅导员联系下,于是我就打过去了,辅导员在开会。。要等10分钟。。等十分钟= =,然后我就在那等。。一帮领导在坐着,我就在门口等。。那个头头实在看不下去了(应该是我碍眼了),说,你回去吧,有什么问题,让辅导员直接和他联系。于是我就去找辅导员了,然后说了下情况,我就回实验室了,然后下午的课我给忘了= =,都没有想到上课的事。。然后老师又点名了-  -,我也是第一次不去。。。无语啊。。 周四,辅导员说,还是不行,我无奈,因为辅导员能力有限,所以他也改变不了什么,于是,我再一次找到那个头头,他说,应该是系统问题,然后让我去找做系统的我们学院的某个老师,我把消息转达辅导员,然后准备去找那个老师,辅导员看看我也蛮累的,就说,我来吧,你回去等消息吧。。等消息。。。这句话听上去就像,都别烦了,没了就没了吧。。。这怎么能行,我还指望这钱买衣服的。于是,我每隔3小时一个电话。 终于,到了周五中午,在我绝望的时候,他的一条短信“OK了,申请吧”,让我体会到了找到系统bug的快感,我终于第一次找到了一个现行 的系统bug,那就是在筛选名单时,没有对成绩一栏的标志符进行判断,直接读入了数据库中的数据,导致了某些人某些超修课依旧能在系统中检索到。 或者说,他为了加快速度,直接做了缓存,不进行实时更新。反正有一点可以肯定。在超修课不及格的情况下,系统是不正常运行的。 要改变,只有定期刷新,因为数据量比较大,实时不太可能。 真的觉得,做一个没有bug的系统,还真的是很困难。 不过,最开心的,我终于完成了我大学的一个目标,最一个第一,我是我们学校第一个两门0分,照拿奖学金的人,最后还是个特等!!

算法-卡特兰数(组合数学)

常见的问题,HDOJ 1133 他的递推关系式为: 几种常见的题目类型: 括号化 矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案? 出栈顺序 一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列? 突多边形三角划分(握手问题) 在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数f(n)。 圆桌周围有 2n个人,他们两两握手,但没有交叉的方案数。 给定节点组成二叉树 给定N个节点,能构成多少种不同的二叉树? 拥有n+1个叶子节点的二叉树数量 4个叶子节点的所有二叉树形态 n*n的方格地图中,从一个角到另外一个角,不跨越对角线的路径数 4×4方格地图中的路径有: 接下来是几道笔试题: 先来一道阿里巴巴的笔试题目:说16个人按顺序去买烧饼,其中8个人每人身上只有一张5块钱,另外8个人每人身上只有一张10块钱。烧饼5块一 个,开始时烧饼店老板身上没有钱。16个顾客互相不通气,每人只买一个。问这16个人共有多少种排列方法能避免找不开钱的情况出现。 > C8=1430,所以总数=1430×8!x8! 在图书馆一共6个人在排队,3个还《面试宝典》一书,3个在借《面试宝典》一书,图书馆此时没有了面试宝典了,求他们排队的总数? > C5=30,所以总数为: 5×3!x3!=180.