四种方法求最长回文串

海天一树

发布于 2018-04-17 11:19:15

1K0

发布于 2018-04-17 11:19:15

文章被收录于专栏：海天一树海天一树

所谓回文串，就是正着读和倒着读结果都一样的回文字符串。比如： 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算法

Manacher算法的时间复杂度为O(N)，具体可参考： https://www.cnblogs.com/grandyang/p/4475985.html

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2018-03-05，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自海天一树微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度