最长回文最长回文字符串

回文串就是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。回文子串，顾名思义，即字符串中满足回文性质的子串。比如输入字符串 "google”，由于该字符串里最长的对称子字符串是 "goog”，因此输出4。

1.问题解决的基本方法

分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。
要判断一个字符串是不是对称的，不是一件很难的事情。我们可以先得到字符串首尾两个字符，判断是不是相等。如果不相等，那该字符串肯定不是对称的。否则我们接着判断里面的两个字符是不是相等，以此类推。

/*
 *作者：侯凯
 *说明：求最长回文字符串
 *日期：2013-10-15
*/
#include<iostream>
using namespace std;
//字符串是否对称
bool isAym(char *cbegin, char *cend)
{
    if(cbegin == NULL || cend ==NULL || cbegin > cend)
    {
        return false;
    }
    while(cbegin<cend)
    {
        if(*cbegin!=*cend)
        {
            return false;
        }
        cbegin++;
        cend--;
    }
    return true;
}

现在我们试着来得到对称子字符串的最大长度。最直观的做法就是得到输入字符串的所有子字符串，并逐个判断是不是对称的。如果一个子字符串是对称的，我们就得到它的长度，最后经过比较，就能得到最长的对称子字符串的长度了。

//O(n*n*n)复杂度的子字符串
int getMaxSym(char * str)
{
    if(str == NULL)
        return 0;
    int maxlength = 0, strlength = 0;
    char *pFirst = str;
    char *strEnd = str + strlen(str);
    while(pFirst < strEnd)
    {
        char *pLast = strEnd;
        while(pLast > pFirst)
        {
            if(isAym(pFirst, pLast))
            {
                strlength = pLast - pFirst + 1;
                if(strlength > maxlength)
                {
                    maxlength = strlength;
                }
            }
            pLast --;
        }
        pFirst ++;
    }
    return maxlength;
}

上述方法的时间效率：由于需要两重while循环，每重循环需要O（n）的时间。另外，我们在循环中调用了IsSym，每次调用也需要O（n）的时间。因此整个函数的时间效率是O（n^3）。
假设输入：abcddcba，按照上述程序，要分割成 'abcddcba’, 'bcddcb’, 'cddc’, 'dd’…等字符串，并对这些字符串分别进行判断。不难发现，很多短子字符串在长些的子字符串中比较过，这导致了大量的冗余判断，根本原因是：对字符串对称的判断是由外向里进行的。
换一种思路，从里向外来判断。也就是先判断子字符串(如dd)是不是对称的。如果它(dd)不是对称的，那么向该子字符串两端各延长一个字符得到的字符串肯定不是对称的。如果它(dd)对称，那么只需要判断它(dd)两端延长的一个字符是不是相等的，如果相等，则延长后的字符串是对称的。

2.改进的解决方案

根据从里向外比较的思路写出如下代码：

//改进后的程序
int getMaxSym2(char * str)
{
    if(str == NULL)
        return 0;
    int maxlength = 0;
    char *ptag = str;
    while(*ptag !='

1.问题解决的基本方法

/*
 *作者：侯凯
 *说明：求最长回文字符串
 *日期：2013-10-15
*/
#include<iostream>
using namespace std;
//字符串是否对称
bool isAym(char *cbegin, char *cend)
{
    if(cbegin == NULL || cend ==NULL || cbegin > cend)
    {
        return false;
    }
    while(cbegin<cend)
    {
        if(*cbegin!=*cend)
        {
            return false;
        }
        cbegin++;
        cend--;
    }
    return true;
}

//O(n*n*n)复杂度的子字符串
int getMaxSym(char * str)
{
    if(str == NULL)
        return 0;
    int maxlength = 0, strlength = 0;
    char *pFirst = str;
    char *strEnd = str + strlen(str);
    while(pFirst < strEnd)
    {
        char *pLast = strEnd;
        while(pLast > pFirst)
        {
            if(isAym(pFirst, pLast))
            {
                strlength = pLast - pFirst + 1;
                if(strlength > maxlength)
                {
                    maxlength = strlength;
                }
            }
            pLast --;
        }
        pFirst ++;
    }
    return maxlength;
}

2.改进的解决方案

根据从里向外比较的思路写出如下代码：

//改进后的程序
int getMaxSym2(char * str)
{
    if(str == NULL)
        return 0;
    int maxlength = 0;
    char *ptag = str;
    while(*ptag !='

最长回文 最长回文字符串

相关推荐

最长回文最长回文字符串