最长回文子串

0
8

本题我采用从不同中心不断扩展的方法去进行求解,程序代码如下,在写程序的时候我遇到的一个坑是,由于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;
}

<

发布回复

请输入评论!
请输入你的名字