缘起

无聊, 研究一下随机化算法. poj 3318 Matrix Multiplication

Read More

缘起

【1】中已经极为初步的介绍了ac自动机这种数据结构. 并且给出了板子. 那么自然需要验证一下板子的正确性. hdu 2222 Keywords Search

Read More

缘起

【1】中使用后缀树切了~ 但是本文采用后缀数组的姿势切. 切法的思想源自罗大神的IOI09年论文的第18页. 即通过lcp数组对后缀进行分类的思想.

Read More

缘起

曾经使用后缀树&后缀数组（见【2】和【1】）尝试切 poj 3461 Oulipo 但是后缀树直接MLE， 后缀数组被T掉了. 而且关于原因，在【1】和【2】中都做了详细的说明. 没办法，在精确匹配领域，kmp的确是不折不扣的大佬.

向 kmp 大佬低头~ kmp牛逼！

Read More

缘起

最长公共子串问题是著名的问题. 在【1】中使用DP给出了一种O(n^2)解法, 但显然这种解法不能处理1e5以上的字符串. 搓了 后缀数组的板子之后，来搞 洛谷 SP1811 LCS - Longest Common Substring

Read More

缘起

【1】中求LCS的后缀树解法被无情的MLE掉了. 所以我打算学习了后缀数组用后缀树完成对他的一击.

Read More

缘起

继续和字符串算法刚. ac自动机是过不去的坎~

Read More

缘起

本想在【2】中一口气验证【3】中搓的da、dc3两块板子，但是class中自定义sort又不会写~ 只好作罢~ 【2】中仅仅证明了【3】中的dc3的板子是正确无误的. 下面又拿起了【1】中的题目——求最长重复出现子串（允许重叠）。【1】中已经用后缀树切了它（但是被T掉了），现在再用后缀数组来切它一次.

Read More

缘起

日常浪费生命~ lintcode 928. 最多有两个不同字符的最长子串

Read More

缘起

日常浪费生命~ lintcode 384. 最长无重复字符的子串

Read More