KMP字符串匹配算法和JDK

一般的朴素字符串匹配算法: 从目标串Target的第一个字符开始扫描,逐一与模式串的对应字符进行匹配,若该组字符匹配,则检测下一组字符 如遇失配,则退回到Target的第二个字符,重复上述步骤,直到整个Pattern在Target中找到匹配,或者已经扫描完整个目标串也没能够完成匹配为止 算法理解起来很简单,实现起来也容易,但是其中包含了过多不必要的操作,也就是在目标串中,有些字符是可以直接跳过,不必检测的 但是在特定的情况下,这样的算法还是有可优化的地方的. 不妨假设我们的目标串:Target = “a b c d e a b c d e a b c…

一切都是奖学金惹的祸

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

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

常见的问题,HDOJ 1133 他的递推关系式为: 几种常见的题目类型: 括号化 矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案? 出栈顺序 一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列? 突多边形三角划分(握手问题) 在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数f(n)。 圆桌周围有 2n个人,他们两两握手,但没有交叉的方案数。 给定节点组成二叉树 给定N个节点,能构成多少种不同的二叉树? 拥有n+1个叶子节点的二叉树数量 4个叶子节点的所有二叉树形态 n*n的方格地图中,从一个角到另外一个角,不跨越对角线的路径数 4×4方格地图中的路径有: 接下来是几道笔试题:…