最长回文子串

本题我采用从不同中心不断扩展的方法去进行求解，程序代码如下，在写程序的时候我遇到的一个坑是，由于string的length()函数返回值并非int型数值，因此一开始直接使用min()函数会报错，经过强制类型转换后便可以不报错。时间复杂度为O(n)马拉车算法留作以后再进行学习～～～～～

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;
string longestPalindrome(string s);

int main()
{
    string s;
    cin>>s;
    cout<<longestPalindrome(s);
    return 0;
}

string longestPalindrome(string s) 
{
    if(s.length()==0) return "";
    int max_length = 0;
    int ex = 0;
    int position = 0;
    bool flag = false;
    for(int i = 0;i<s.length();++i)
    {
        int expand = 0;
        while(expand<= min(i, (int)(s.size()-1-i)))
        {
            if(s[i+expand]==s[i-expand])
            {
                if(expand*2+1>max_length)
                {
                    max_length = expand*2+1;
                    ex = expand;
                    position = i;
                    expand++;
                }
                else expand++;
            }
            else break;
        }
    }
    string ans = s.substr(position-ex,max_length);
    for(int i = 1;i<s.length();++i)
    {
        int expand = 1;
        while(expand<= min(i, (int)(s.size()-i)))
        {
            if(s[i+expand-1]==s[i-expand])
            {
                if(expand*2>max_length)
                {
                    max_length = expand*2;
                    if(!flag) flag = true;
                    ex = expand;
                    position = i;
                    expand++;
                }
                else expand++;
            }
            else break;
        }
    }
    if (flag)
    {
        ans = s.substr(position-ex,max_length);
    }
    return ans;
}

 

原文链接:https://www.cnblogs.com/gxyssd/p/12694127.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有