回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。 输入一个字符串Str，输出Str里最长回文子串的长度。 Input 输入Str（Str的长度 <= 100000) Output 输出最长回文子串的长度L。 Input示例 daabaac Output示例 5
求最长回文字符串的长度，只介绍几种自己经常用到的算法。
1.中心扩展法(时间复杂度(O(n^2)))
#include <bits/stdc++.h> const int N = 1e3 + 10; using namespace std; char s[N]; int main() { int n,m; while(~scanf("%s",s)) { int maxx = 0; int m = strlen(s); for(int i = 0;i < m;i ++) { //奇数的时候 for(int j = 0;i - j >= 0 && i + j < m;j ++) { if(s[i - j] != s[i + j]) break; if(2 * j + 1 > maxx) maxx = 2 * j + 1; } //偶数的时候 for(int j = 0;i - j >= 0 && i + j + 1 < m;j ++) { if(s[i - j] != s[i + j + 1]) break; if(j * 2 + 2 > maxx) maxx = 2 * j + 2; } } printf("%d\n",maxx); } }
2.Manacher算法(时间复杂度(O(n)))
该算法非常不错的一个解释：链接
#include <bits/stdc++.h> //注意开数组的长度，要开到题目中要求回文字符串长度的二倍以上 const int N = 3e5; using namespace std; char str[N],s[N]; // p[i] 来记录以字符str[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]），即回文字符串的一半长度 int p[N]; //str字符串预处理 void Have_s() { int j = 0,len = strlen(s); str[j ++] = '$'; str[j ++] = '#'; for(int i = 0; i < len; i ++) str[j ++] = s[i],str[j ++] = '#'; str[j] = '\0';//不要忘了 } //Manacher算法核心 void Manacher() { //id表示最大回文子串中心的位置，mx则为id+P[id]，也就是最大回文子串的边界 int id = 0,mx = 0,len = strlen(str); for(int i = 1; i < len; i ++) { //p[2*id-i]没有到达边界 //mx - i表示到达边界，此时暴力往两边查找是否仍然满足回文 if(mx > i) p[i] = min(p[2*id-i],mx - i); else p[i] = 1; //暴力 for(; str[i -p[i]] == str[i + p[i]]; p[i] ++); //更新此时所能到达的最大边界mx if(mx < i + p[i]) { mx = i + p[i]; id = i; } } int ans = 0,n = 0; for(int i = 0; i < len; i ++) if(ans < p[i]) { ans = p[i]; n = i; } printf("%d\n",ans - 1); //下面是输出最长回文字符串的方法 // ans --; // int k = n - ans; // int t = n + ans; // for(int i = k; i <= t; i ++) // if(str[i] != '#') // printf("%c",str[i]); // printf("\n"); } int main() { while(~scanf("%s",s)) { memset(str,0,sizeof(str)); Have_s(); Manacher(); } return 0; }3. 动态规划(时间复杂度(O(n^2)))
回文串就是正着读和反着读一样的字符串，如“abba”，"abcba"，最长回文子串是字符串的子串中最长的属于回文串的子串。如字符串"abbaabccba"的最长回文子串为"abccba"，本文采用动态规划算法来查找最长回文子串，算法时间复杂度为O（n²）。设状态dp[j][i]表示索引j到索引i的子串是否是回文串。
则易得状态转移方程如下：
则dp[j][i]为true时表示索引j到索引i形成的子串为回文子串，且子串起点索引为i,长度为i-j+1。
#include <iostream> #include <algorithm> #include <string.h> using namespace std; int dp[1010][1010]; void longestPalindrome(string str) { int n = str.size(); int start = 0; int max_length = 1; memset(dp, 0, sizeof(dp)); for(int i = 0; i < n; i ++) { for(int j = 0; j <= i; j ++) { if(i-j<=1) dp[j][i]=(str[i]==str[j]); else dp[j][i]=(str[i]==str[j] && dp[j+1][i-1]); if(dp[j][i] && max_length<(i-j+1)) { max_length=i-j+1; start=j; } } } // 输出回文字符串的最大长度 cout << max_length << endl; // 输出回文字符串 cout << str.substr(start, max_length) << endl; } int main() { string s; while(cin >> s) { longestPalindrome(s); } }