51nod 1088 1089 最长回文子串 后缀树

缘起

最长回文子串是亚马逊的面试题. 在【1】和【2】中分别使用了DP、马拉车两种解法. 虽然基本DP会T, 加上明显的暴力. 已经有三种解法了. 但是最长回文子串的正常解法还是后缀树和后缀数组（貌似后缀数组更加流行一点, 后缀树的缺点在【3】中已经吐槽过了） 但是本文想借 51nod 1088 最长回文子串 来练习一下后缀树. 以证明【3】中的后缀树的板子正确无误（【1】中的板子在 【4】的基础上精简了一些）.

Read More

poj 3461 Oulipo 后缀树 KMP

缘起

再也不水题了~ 立个flag, 潜心要搞定 字符串和各种平衡树（啥树套树、替罪羊、主席树、树剖啥的）~ 首先拿字符串开刀. 字符串算法其实贼难了~ 然后最近学习后缀树. 【1】中其实敲了一个后缀树 ukk的板子。 现在用它来找题来切. 但是无奈网上用后缀树切的题不多（大部分都是后缀数组）. 所以我找到【2】中说的后缀树的四大运用。来逐个找题切来提高对后缀树的理解. 首先从kmp板题 poj 3461 Oulipo 开始吧~

Read More