1. 全栈程序员必看首页

四种方法求最长回文子串

全栈程序员-用户IM • • 未分类

四种方法求最长回文子串所谓回文串，就是正着读和倒着读结果都一样的回文字符串。比如：a,aba,abccba都是回文串，ab,abb,abca都不是回文串。一、暴力法最容易想到的就是暴力破解，求出每一个子串，之后判断是不是回文，找到最长的那个。求每一个子串时间复杂度O(N^2),判断子串是不是回文O(N)，两者是相乘关系，所以时间复杂度为O(N^3)。stringlongestPali…

大家好，又见面了，我是你们的朋友全栈君。

所谓回文串，就是正着读和倒着读结果都一样的回文字符串。
比如：
a, aba, abccba都是回文串，
ab, abb, abca都不是回文串。

一、暴力法

最容易想到的就是暴力破解，求出每一个子串，之后判断是不是回文，找到最长的那个。

求每一个子串时间复杂度O(N^2), 判断子串是不是回文O(N)，两者是相乘关系，所以时间复杂度为O(N^3)。

string longestPalindrome(string &s)
{
    int len = s.size();                  //字符串长度
    int maxlen = 1;                      //最长回文字符串长度
    int start = 0;                       //最长回文字符串起始地址
    for(int i = 0; i < len; i++)         //起始地址
    {
        for(int j = i + 1; j < len; j++) //结束地址
        {
            int tmp1 = i, tmp2 = j;
            while(tmp1 < tmp2 && s.at(tmp1) == s.at(tmp2))//判断是不是回文
            {
                tmp1++;
                tmp2--;
            }

            if(tmp1 >= tmp2 && j - i + 1 > maxlen)
            {
                maxlen = j - i + 1;
                start = i;
            }
        }
    }

    return s.substr(start, maxlen);
}

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的子串是否是回文串。则转移方程为：

四种方法求最长回文子串

 

则dp[j][i]为true时表示索引j到索引i形成的子串为回文子串，且子串起点索引为j,长度为i – j + 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 maxlen = 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] && maxlen < i - j + 1)
            {
                maxlen = i - j + 1;
                start = j;
            }
        }
    }

    return s.substr(start, maxlen);
}

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 len = s.size();
    int maxlen = 1;
    int start = 0;

    for(int i = 0; i < len; i++)//求长度为奇数的回文串
    {
        int j = i - 1, k = i + 1;
        while(j >= 0 && k < len && s.at(j) == s.at(k))
        {
            if(k - j + 1 > maxlen)
            {
                maxlen = k - j + 1;
                start = j;
            }

            j--;
            k++;
        }
    }

    for(int i = 0; i < len; i++)//求长度为偶数的回文串
    {
        int j = i, k = i + 1;
        while(j >= 0 && k < len && s.at(j) == s.at(k))
        {
            if(k - j + 1 > maxlen)
            {
                maxlen = k - j + 1;
                start = j;
            }

            j--;
            k++;
        }
    }

    return s.substr(start, maxlen);
}


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 len = s.size();
    int maxlen = 1;
    int start = 0;

    for(int i = 0; i < len; i++)//求长度为奇数的回文串
    {
        int j = i - 1, k = i + 1;
        while(j >= 0 && k < len && s.at(j) == s.at(k))
        {
            if(k - j + 1 > maxlen)
            {
                maxlen = k - j + 1;
                start = j;
            }

            j--;
            k++;
        }
    }

    for(int i = 0; i < len; i++)//求长度为偶数的回文串
    {
        int j = i, k = i + 1;
        while(j >= 0 && k < len && s.at(j) == s.at(k))
        {
            if(k - j + 1 > maxlen)
            {
                maxlen = k - j + 1;
                start = j;
            }

            j--;
            k++;
        }
    }

    return s.substr(start, maxlen);
}


int main()
{
    string s;
    cout << "Input source string: ";
    cin >> s;
    cout << "The longest palindrome: " << longestPalindrome(s);
    return 0;
}

 

四、Manacher算法

Manacher算法的时间复杂度为O(N)，具体可参考：

https://blog.csdn.net/S_999999/article/details/83472651

#include <iostream>  
#include <cstring>
#include <algorithm>  
 
using namespace std;
 
char s[1000];
char s_new[2000];
int p[2000];
 
int Init()
{
    int len = strlen(s);
    s_new[0] = '$';
    s_new[1] = '#';
    int j = 2;
 
    for (int i = 0; i < len; i++)
    {
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }
 
    s_new[j] = '
#include <iostream>  
#include <cstring>
#include <algorithm>  
using namespace std;
char s[1000];
char s_new[2000];
int p[2000];
int Init()
{
int len = strlen(s);
s_new[0] = '$';
s_new[1] = '#';
int j = 2;
for (int i = 0; i < len; i++)
{
s_new[j++] = s[i];
s_new[j++] = '#';
}
s_new[j] = '\0';  // 别忘了哦
return j;  // 返回 s_new 的长度
}
int Manacher()
{
int len = Init();  // 取得新字符串长度并完成向 s_new 的转换
int max_len = -1;  // 最长回文长度
int id;
int mx = 0;
for (int i = 1; i < len; i++)
{
if (i < mx)
p[i] = min(p[2 * id - i], mx - i);  // 需搞清楚上面那张图含义, mx 和 2*id-i 的含义
else
p[i] = 1;
while (s_new[i - p[i]] == s_new[i + p[i]])  // 不需边界判断，因为左有'$',右有'\0'
p[i]++;
// 我们每走一步 i，都要和 mx 比较，我们希望 mx 尽可能的远，这样才能更有机会执行 if (i < mx)这句代码，从而提高效率
if (mx < i + p[i])
{
id = i;
mx = i + p[i];
}
max_len = max(max_len, p[i] - 1);
}
return max_len;
}
int main()
{
while (printf("请输入字符串：\n"))
{
scanf("%s", s);
printf("最长回文长度为 %d\n\n", Manacher());
}
return 0;
}

';  // 别忘了哦
    
    return j;  // 返回 s_new 的长度
}
 
int Manacher()
{
    int len = Init();  // 取得新字符串长度并完成向 s_new 的转换
    int max_len = -1;  // 最长回文长度
 
    int id;
    int mx = 0;
 
    for (int i = 1; i < len; i++)
    {
        if (i < mx)
            p[i] = min(p[2 * id - i], mx - i);  // 需搞清楚上面那张图含义, mx 和 2*id-i 的含义
        else
            p[i] = 1;
 
        while (s_new[i - p[i]] == s_new[i + p[i]])  // 不需边界判断，因为左有'$',右有'
#include <iostream>  
#include <cstring>
#include <algorithm>  
using namespace std;
char s[1000];
char s_new[2000];
int p[2000];
int Init()
{
int len = strlen(s);
s_new[0] = '$';
s_new[1] = '#';
int j = 2;
for (int i = 0; i < len; i++)
{
s_new[j++] = s[i];
s_new[j++] = '#';
}
s_new[j] = '\0';  // 别忘了哦
return j;  // 返回 s_new 的长度
}
int Manacher()
{
int len = Init();  // 取得新字符串长度并完成向 s_new 的转换
int max_len = -1;  // 最长回文长度
int id;
int mx = 0;
for (int i = 1; i < len; i++)
{
if (i < mx)
p[i] = min(p[2 * id - i], mx - i);  // 需搞清楚上面那张图含义, mx 和 2*id-i 的含义
else
p[i] = 1;
while (s_new[i - p[i]] == s_new[i + p[i]])  // 不需边界判断，因为左有'$',右有'\0'
p[i]++;
// 我们每走一步 i，都要和 mx 比较，我们希望 mx 尽可能的远，这样才能更有机会执行 if (i < mx)这句代码，从而提高效率
if (mx < i + p[i])
{
id = i;
mx = i + p[i];
}
max_len = max(max_len, p[i] - 1);
}
return max_len;
}
int main()
{
while (printf("请输入字符串：\n"))
{
scanf("%s", s);
printf("最长回文长度为 %d\n\n", Manacher());
}
return 0;
}

'
            p[i]++;
 
        // 我们每走一步 i，都要和 mx 比较，我们希望 mx 尽可能的远，这样才能更有机会执行 if (i < mx)这句代码，从而提高效率
        if (mx < i + p[i])
        {
            id = i;
            mx = i + p[i];
        }
 
        max_len = max(max_len, p[i] - 1);
    }
 
    return max_len;
}
 
int main()
{
    while (printf("请输入字符串：\n"))
    {
        scanf("%s", s);
        printf("最长回文长度为 %d\n\n", Manacher());
    }
    return 0;
}

 

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/135212.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0
blank

相关推荐

  • JAVA/request.getParameterValues

    JAVA/request.getParameterValues

    JAVA/request.getParameterValues1比较request.getParameterValues与request.getParameterrequest.getParameterValues(Stringname)是获得如checkbox类（名字相同，但值有多个）的数据。request.getParameter(Stringname)是获得对应名字的值，如果有重复的名，则返回第一个值。例如：reque

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年7月22日
  • 两个正序数组 找中位数_两个有序数组的中位数

    两个正序数组 找中位数_两个有序数组的中位数

    两个正序数组 找中位数_两个有序数组的中位数原题连接给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。示例 1：输入：nums1 = [1,3], nums2 = [2]输出：2.00000解释：合并数组 = [1,2,3] ，中位数 2示例 2：输入：nums1 = [1,2], nums2 = [3,4]输出：2.50000解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5示例 3：输入：nums1 = [0,

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年8月8日
  • service network restart重启失败_network restart

    service network restart重启失败_network restart

    service network restart重启失败_network restartLinux重启网络服务用systemctlrestartnetworkingUbuntuServer:Failtorestartnetworking.service:Unitnetwork.servicenotfound

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年8月30日
  • Apache Struts2再爆高危漏洞

    Apache Struts2再爆高危漏洞

    Apache Struts2再爆高危漏洞60网站安全检测最新struts2命令执行漏洞分析时间：2013-07-1809:46 在struts2中，DefaultActionMapper类支持以”action:”、”redirect:”、”redirectAction:”作为导航或是重定向前缀，但是这些前缀后面同时可以跟OGNL表达式，由于struts2没有对这些前缀做过滤，

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年7月13日
  • 如何用51单片机控制步进电机运动「建议收藏」

    如何用51单片机控制步进电机运动「建议收藏」

    如何用51单片机控制步进电机运动「建议收藏」本来接触单片机挺久了的，但是一直只是停留在非常初级的认识阶段，本科的时候上过几门课，但是从来没有自己捣鼓过单片机，这次突然来了兴趣，感觉一下子学到了好多东西，在这里好好整理一下。这篇文章只适合于入门阶段的小白阅读，高手请绕道。12年年初的时候购买了一套普中科技的“单片机开发试验仪”，好多次想好好学学，结果每一次都半途而废，主要原因还是周围的人都不会用，有问题都不知道找谁问，结果锁到箱子里一直到现在。

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年6月1日
  • matlab三维图形的绘制[通俗易懂]

    matlab三维图形的绘制[通俗易懂]

    matlab三维图形的绘制[通俗易懂]采用matlab进行三维图绘制mesh函数：网格图mesh(x,y,z)x是n维向量，y是m维向量，z是m*n维向量等高线，底座surf函数：曲面符号隐函数绘图

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年10月11日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号