【LEMH·C＋】Manacher算法

哈，二月到了，集训也结束了，我终于可以起飞了。

今天我们来说说manacher算法。

这是一种字符串算法，可以用O（n）的复杂度求出一串字符中最大回文串的长度。今天的题目：

题目内容就是求一个字符串中最大回文子串的长度，我们来看看数据范围：

如果我们用最暴力的方法写，枚举l和r两个区间，复杂度大概是O（n^3），明显一组数据都过不去。

所以我们就要使用我们有趣的manacher算法。那怎么实现呢？因为回文串有2种情况，奇数和偶数，如何避免这一步呢？其实也很简单，只需要在字符串中添加一个字符就可以了。比如：abcba这个字符串，我们就可以转化为#a#b#c#b#a#，至于为什么前后都要加上符号，后面会提到。代码如下：

然后我们不就省去的判断奇偶的操作了吗？然后我们会出现一个新的问题：如何避免子串被多次访问呢？这个问题，我们就可以使用一个数组来记录当前点最大拓展出的回文子串的长度，所以我们需要使用两个变量maxi和maxr，来记录拓展出的子串。

真的需要两个吗？其实不需要，只需要记录maxr就可以了，我们可以通过计算算出来。然后我们就可以使用1层循环，来遍历整个数组，每次都只需要更新一下maxr和中心点mid就可以了，代码如下：

是不是瞬间豁然开朗呢？所以这题模板还是十分简单的，如果会了模板，这道题就可以顺手切了：

小编AC此题是用了一个特判，后两个洛谷自己添加的数据太毒瘤了，过了后两个第5个点又WA了······

那么今天的更新就到这里，同时快过年了，祝大家多多爆0。