思路
一道kmp的裸题，主要是学习kmp的使用方法。kmp的精髓在于使用了一个next数组。这个next数组的计算是放在预处理中的。next数组中记录的是不同长度下最长的前后缀的位置。举个例子：
字符串：a b c d a b d
next 0 0 0 0 1 2 0
你看到了什么？后边的两个a，b对应了开头的公共前缀的长度。那么这个next数组该怎么用？当你做字符串匹配的时候，如果发现当前位置字符与模板字符串不同，那么你可以把指向模板字符串的指针挪到之前公共长度（也就是next数组对应的地方）继续匹配，这样就避免了公共的前缀重复匹配浪费时间。
这里着重讲一下next数组怎么求。next数组的求法稍微有点绕，我放下我的代码
void makenext() {
int q, k;
nexts[0] = 0;
for (q = 1, k = 0;q < m;q++) { while (k > 0 && b[q] != b[k])k = nexts[k - 1];
if (b[q] == b[k])k++;
nexts[q] = k;
}
}
代码中的while循环是非常绕的，他的意思是什么呢？在求前后缀的时候，因为b[q]!=b[k]，也就是前后缀有失配的地方，这个时候你之前算的一长串已经不能用了，所以你要回到之前求的短串再来尝试匹配。
HDU - 3068 最长回文
思路：
一道神奇的回文题，使用O(n^2)复杂度的算法会超时，需要使用manacher算法。manacher算法简而言之就是利用了已经获得的回文字符串左右对称的性质，观察现在所在的字符是不是在已有回文串中，利用回文串左边求得的回文长度来初始化右边来减少重复计算，需要记录当前会问能达到的最右端。复杂度为O(n)，因为最右端最多移动n次，所以复杂度很低。