Sunday算法是1990年才发明的. 据说效率比BM、KMP更快的算法. 最重要的还是好理解. BM算法以及下篇文章要讲解的Horspool算法都是后缀匹配算法.但是Sunday算法是前缀匹配算法. Sunday算法的移动并不是依据失配字符，而是基于即将要参与进行匹配的字符（确切讲是失配字符的后一个字符）. 所以这样会更简洁.

我也很纳闷——Sunday算法这么高效而且简洁，为什么没有早点被人发明?

2019-07-07

分治+扩展KMP 最长回文子串 hdu 3294 Girls' research

缘起

【1】中已经给出了扩展KMP的板子, 【2】中验证了它的性能. 这里使用分治+扩展KMP给出最长回文子串的算法. 关于最长回文子串，【3】中已经给出了一种算法——manacher（马拉车算法）. 这里给出分治+扩展KMP算法.

于是我找到了 hdu 3294 来试试这种算法

这个算法显然没有马拉车来的简单，但仅仅是练习扩展KMP而已.

2019-07-07

字符串匹配之 Rabin-Karp算法（RK）

缘起

关于字符串匹配的算法，我们之前介绍了KMP、BM、扩展KMP（注意，扩展KMP和KMP本质上讲不是一个思路，其实扩展KMP不仅有着和KMP一样的性能，而且比KMP需要的数学推导更加简单）.

毫无例外的涉及失配情形下的跳转推导. 较为复杂, 本文介绍一种基于哈希的”暴力” 算法. 但是有着不错的性能和极为简单的实现, 就是著名的KR算法，由Karp和Rabin发明.

2019-07-07

扩展KMP算法 hdu 2594 Simpsons’ Hidden Talents

缘起

【1】中我们通过严格的数学推导引入了扩展KMP算法. 自然需要一块板子来试试【1】中写的算法有没有漏洞. 于是找到了 hdu2594

2019-07-07

扩展KMP问题

缘起

【1】中我们已经分析了KMP算法. 下面考虑扩展KMP问题.

1
2

给定母串T，和子串p, 0索引不用于存储数据, 定义n=|T|（strlen(T)）, m=|p|，extend[i]=T[i..n]与p的最长公共前缀长度(LCP),即extend[i]=LCP(T[i,...,n], p[1,...,m])
请在线性的时间复杂度内，求出所有的extend[1..n].

2019-07-06

缓存淘汰算法之 LRU算法 leetcode 146. LRU Cache

缘起

因为作为一个java工程师，缓存组件是必须要深入理解的. 提到缓存的话，有两点必须要考虑

缓存和持久化数据的一致性问题
缓存数据的过期问题，这就涉及淘汰算法. 因为缓存大小是有限的.

常见的淘汰算法有 FIFO、LRU、LFU（具体含义见【1】），一个优秀的缓存框架（例如ehcache）必须要实现这三种淘汰算法.

这里的题目涉及LRU算法的数据结构的设计.

ps: 这里多说一句，在操作系统的内存管理中，有一类很重要的算法就是内存页面置换算法（包括FIFO，LRU,LFU等几种常见页面置换算法）。事实上，Cache算法和内存页面置换算法的核心思想是一样的：都是在给定一个限定大小的空间的前提下，设计一个原则如何来高效地更新和访问其中的元素。

传送门