求解一个字符串中最长的回文字串
暴力法 首先给定一个字符串str，设其长度为n，我们可以通过比较s[0]和s[n-1]，s[1]和s[n-2]…来判断str是否为回文。 如果我们要得到一个字符串text中最长的回文子串的话，通过枚举text的所有子串subText，然后判断其是否为回文，统计最长的一条即可。 一个长度为ｎ（ｎ＞＝２）的字符串，其长度为ｉ的子串有ｎ－ｉ＋１个，ｉ＝２～ｎ，所以枚举的复杂度为 O(n2) 。中心扩展法 由于奇数长度的回文一定有一个中心字符，所以可以以某个字符串为中心向两边扩展，得到以这个字符为中心的最长回文子串。 这样的方法有两个问题。 问题一：偶数长度的回文串需要另外处理。 因为偶数长度回文没有中心字符。可以通过在每个字符串之间添加特殊字符（不在字符串的字母表中）进行处理，然后我们用数组r来记录以第i个字符为中心的最长回文半径（包括自身，这样可以使得i＋ｒ［ｉ］为第一个不为回文的字符）。例如：
abba-># a # b # b # a # index:0 1 2 3 4 5 6 7 8 r: 1 2 1 2 5 2 1 2 1 r-1: 0 1 0 1 4 1 0 1 0 babab-># b # a # b # a # b # index: 0 1 2 3 4 5 6 7 8 9 10 r: 1 2 1 4 1 6 1 4 1 2 1 r-1: 0 1 0 3 0 5 0 3 0 1 0这样偶数长度的回文子串变成了以＃为中心的奇数长度的回文字串。而奇数长度的回文字串依然是奇数长度。而且ｒ－１即为原串中最长回文串的长度。 问题二：在扩展时，重复遍历了已经确定为回文的子串。
text: b a b a b a b a b index:0 1 2 3 4 5 6 7 8 iter1: *ptr=b, queried indices: 1 iter2: *ptr=a, queried indices: 0, 2 iter3: *ptr=b, queried indices: 1, 3; 0, 4 iter4: *ptr=a, queried indices: 2, 4; 1, 5; 0, 6 ...在遍历text[3]的时候，从ａ往两边扩展，但这时候已经知道text[2]的回文半径（包括自身）为3，即a在text[2]的回文半径之内，然后text[1]的回文半径为2，由于text[2]为中心对称点，那么text[3]的回文半径至少为2（即 r[3]≥r[1] ），所以iter4中，对index=2, 4的遍历是多余的，从1，5开始遍历即可。 3.Manacher算法
我们以递归的方式来思考这个问题，即已经求出r[0:i-1]时，如何求解r[i]？ 我们令pos为substring(0:i-1)中，其的回文半径能覆盖到最右边的中心字符的位置（即pos + r[pos]最大）（不是r[pos]最大，因为我们需要已知是回文的字符串尽量覆盖到i）。 首先，令mostRight = pos + r[pos]，即我们知道的第一个不是回文的位置。当 i≥mostRight 的时候，我们已经求解的信息对我们来说没有任何帮助，此时需要一个一个向两边遍历（例如上文中的iter2）。 但如果有 i<mostRight ，我们可以利用已经求解的信息来确定r[i]的一个下界。 令j 为i以pos为中心对称的位置，那么有 j=pos−(i−pos)=2∗pos−i 。此时r[j]是知道的，而且我们有text[i]=text[j]，所以如果text[j - k: j + k]（如果j-k小于pos - r[pos]）为回文，那么text[i-k:i+k]必然也是回文，所以有 r[i]≥r[j] ； 如果j-k大于pos - r[pos]，那么超出pos - r[pos]左边的字符与pos + r[pos]（也就是mostRight）右边的字符不一样，那么我们只能确定text[i-k’+1:mostRight-1]为回文(k’=mostRight-i)，所以我们有： r[i]≥min{r[2∗pos−i],mostRight−i} 。确定下届之后再往两边搜索即可。
#include<cstdio> #include<iostream> #include<vector> #include<string> using namespace std; vector<int> radio; string copied; int min(int a, int b) { return a < b ? a : b; } int findLPS(const string& text) { copied.resize(2 * text.size() + 2, '#'); copied[0] = '$'; for (int i = 0; i < text.size(); ++i) { copied[2 * i + 2] = text[i]; } int len = copied.size(); radio.resize(len, 1); int maxRadioPos = 0; // 记录其回文半径能触及到最远位置的中心点位置 int maxRadio = 1; for (int i = 1; i < len; ++i) { int mostRight = maxRadioPos + radio[maxRadioPos]; if (i < maxRight) radio[i] = min(radio[2 * maxRadioPos - i], mostRight - i); else radio[i] = 1; while (i - radio[i] >= 0 && i + radio[i] < len && copied[i + radio[i]] == copied[i - radio[i]]) ++radio[i]; if (maxRadio < radio[i]) maxRadio = radio[i]; if (maxRadioPos + radio[maxRadioPos] < i + radio[i]) maxRadioPos = i; } return maxRadio - 1; } int main() { int num; cin >> num; string text; for (int i = 0; i < num; ++i) { cin >> text; int n = findLPS(text); cout << n << endl; } return 0; }