所谓回文串,就是正着读和倒着读结果都一样的回文字符串。 比如: a, aba, abccba都是回文串, ab, abb, abca都不是回文串。
最容易想到的就是暴力破解,求出每一个子串,之后判断是不是回文,找到最长的那个。
求每一个子串时间复杂度O(N^2),判断子串是不是回文O(N),两者是相乘关系,所以时间复杂度为O(N^3)。
#include <iostream>
using namespace std;
string longestPalindrome(string &s)
{
int length=s.size(); //字符串长度
int maxlength=1; //最长回文字符串长度
int start=0; //最长回文字符串起始地址
for(int i=0; i<length; i++) //起始地址
{
for(int j=i+1; j<length; j++) //结束地址
{
int tmp1,tmp2;
for(tmp1=i,tmp2=j; tmp1<tmp2; tmp1++,tmp2--)//判断是不是回文
{
if(s.at(tmp1)!=s.at(tmp2))
{
break;
}
}
if(tmp1>=tmp2 && j-i>maxlength)
{
maxlength=j-i+1;
start=i;
}
}
}
return s.substr(start,maxlength);
}
int main()
{
string s;
cout << "Input source string: ";
cin >> s;
cout << "The longest palindrome: " << longestPalindrome(s);
return 0;
}
运行结果:
Input source string: abbacdeedc
The longest palindrome: cdeedc
设状态dp[j][i]表示索引j到索引i的子串是否是回文串。则转移方程为:
1.png
则dp[j][i]为true时表示索引j到索引i形成的子串为回文子串,且子串起点索引为j,长度为j+i-1。 算法时间复杂度为O(N ^ 2)。
#include <iostream>
#include <cstring>
using namespace std;
string longestPalindrome(string s)
{
const int n = s.size();
bool dp[n][n];
memset(dp, 0, sizeof(dp));
int max_len=1; //保存最长回文子串长度
int start=0; //保存最长回文子串起点
for(int i=0;i<n;++i)
{
for(int j=0;j<=i;++j)
{
if(i-j<2)
{
dp[j][i]=(s[i]==s[j]);
}
else
{
dp[j][i]=(s[i]==s[j] && dp[j+1][i-1]);
}
if(dp[j][i] && max_len<(i-j+1))
{
max_len=i-j+1;
start=j;
}
}
}
return s.substr(start,max_len);
}
int main()
{
string s;
cout << "Input source string: ";
cin >> s;
cout << "The longest palindrome: " << longestPalindrome(s);
return 0;
}
中心扩展就是把给定的字符串的每一个字母当做中心,向两边扩展,这样来找最长的子回文串。算法复杂度为O(N^2)。 需要考虑两种情况: 长度为奇数的回文串,比如a, aba, abcba 长度为偶数的回文串,比如aa, abba
#include <iostream>
#include <cstring>
using namespace std;
string longestPalindrome(string &s)
{
const int length=s.size();
int maxlength = 1;
int start = 0;
for(int i=0;i<length;i++)//求长度为奇数的回文串
{
int j=i-1,k=i+1;
while(j>=0&&k<length&&s.at(j)==s.at(k))
{
if(k-j+1>maxlength)
{
maxlength=k-j+1;
start=j;
}
j--;
k++;
}
}
for(int i=0;i<length;i++)//求长度为偶数的回文串
{
int j=i,k=i+1;
while(j>=0&&k<length&&s.at(j)==s.at(k))
{
if(k-j+1>maxlength)
{
maxlength=k-j+1;
start=j;
}
j--;
k++;
}
}
return s.substr(start,maxlength);
}
int main()
{
string s;
cout << "Input source string: ";
cin >> s;
cout << "The longest palindrome: " << longestPalindrome(s);
return 0;
}
Manacher算法的时间复杂度为O(N),具体可参考: https://www.cnblogs.com/grandyang/p/4475985.html