字符串匹配--Sunday算法

2015-12-30
阅读 4 分钟
4.6k
字符串匹配(查找)算法是一类重要的字符串算法(String Algorithm)。有两个字符串, 长度为m的haystack(查找串)和长度为n的needle(模式串), 它们构造自同一个有限的字母表(Alphabet)。如果在haystack中存在一个与needle相等的子串,返回子串的起始下标,否则返回-1。C/C++、PHP中的strstr函数实现的就是这一功能。LeetCode...

Boyer-Moore 算法

2015-11-09
阅读 2 分钟
3.7k
这是一个投票问题,可以模拟我们在投票表决时的计票过程。用一个hash table或者dictionary,数组中的数作为key,它们出现的次数为value。本文想讨论的是下边这些算法。

最长回文子串——Manacher 算法

2015-10-27
阅读 4 分钟
96.9k
对于最长回文子串问题,最简单粗暴的办法是:找到字符串的所有子串,遍历每一个子串以验证它们是否为回文串。一个子串由子串的起点和终点确定,因此对于一个长度为n的字符串,共有n^2个子串。这些子串的平均长度大约是n/2,因此这个解法的时间复杂度是O(n^3)。