题目链接：hdu4513 题意：给出一个n的数的序列，求出一个最长的回文字串，并且满足从[l,mid]单调增（非严格单调，可以相等），[mid,r]单调减（同样是可以相等） 思路：manacher...int型的也是可以搞的。。要求单调的话。。。while扩展的时候判一下就好了。。。 /* *********************************************** Author :111qqz Created Time :2016年04月18日 星期一 20时32分45秒 File Name :code/hdu/4513.cpp …

poj 3294 题意：先做个简单替换，然后求替换后的字符串的最长回文串，以及这个最长回文串的开始和结束位置。 思路：manacher..需要注意的是，返回下标的时候如果字符串长度为偶数，那么中间是没有字符的。。。需要特判一下。。（我的做法是left+(ans%2==0); /* *********************************************** Author :111qqz Created Time :2016年04月18日 星期一 19时40分06秒 File Name :code/hdu/3294.cpp …

poj3974 题意：求最大长度的回文字串。 思路：manacher裸题，用来练习算法。 /* *********************************************** Author :111qqz Created Time :2016年04月18日 星期一 16时32分25秒 File Name :code/poj/3974.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

题目链接 题意：求一个字符串中的最长回文串。 思路：昨天武大校赛遇到了一个manacher算法的题。。。我竟然听都没听过。。。 于是去学习了一发。 感觉这篇博客讲得最详细manachar算法学习 于是切了个模板题练手。 先简单说下我对这个算法的理解，等做一些题目以后再来总结一发。 我觉得manachar算法最关键的一点是，如果你枚举回文串的中心位置，当你枚举到i的时候，那么i之前的位置回文串长度的最大值是已经确定的了。 换句话说，后面的中心位置不会影响前面的中心位置的答案。 于是可以利用前面已经做过的匹配来获得一些信息，避免了重复。 不过讲真。。。O(n)的复杂度。。这算法还是相当让人感到震撼的。。。 更具体的部分见代码注释。。。 …