C++:最大回文字符串

水深无声 2022-05-26 05:19 135阅读 0赞

方法一：

//最长回文子串  
    #include <iostream>  
      
    using namespace std;  
      
    //*s为字符串，n为字符串的长度  
    int LagPalindrome(char *str, int n)  
    {  
        int count = 0;  
        int max = 0;//最长回文子串的长度  
        if (str == NULL || n<1)  
        {  
            return 0;  
        }  
        for (int i = 0; i < n; i++)  
        {         
            //子串为奇数时  
            for (int j = 0; (i-j)>=0&&(i+j)<n; j++)  
            {  
                if (str[i - j] != str[i + j])  
                {  
                    break;  
                }  
                count = 2 * j + 1;  
            }  
            if (count > max)  
            {  
                max = count;  
            }  
            //子串为偶数时  
            for (int k = 0; (i - k)>=0 && (i + k + 1) < n; k++)  
            {  
                if (str[i - k] != str[i + k+1])  
                {  
                    break;  
                }  
                count=2*k + 2;  
            }  
            if (count > max)  
            {  
                max =count ;  
            }  
        }  
          
        return max;  
    }  
      
    int main( )  
    {  
        char str[] = "abccba";  
        int n = strlen(str);  
        int MaxLen;  
        MaxLen = LagPalindrome(str, n);  
          
        cout << "最长回文子串的长度是："<<MaxLen<<endl;  
      
        return 0;  
    }

方法二：

#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;
    }
    
    int getMaxSym2(char * str)
    {
        if(str == NULL)
            return 0;
        int maxlength = 0;
        char *ptag = str;
        while(*ptag !='\0')
        {
            //奇数子字符串
             char *left = ptag - 1;
            char *right = ptag + 1;
            int oddlenght = 1;
            while(left >= str && *right != '\0' && *left == *right)
            {
                left--;
                right++;
                oddlenght += 2;
            }
            if(oddlenght > maxlength)
            {
                maxlength = oddlenght;
            }
            //偶数子字符串
             left = ptag;
            right = ptag + 1;
            int evenlength = 0;
            while(left >= str && *right != '\0' && *left == *right)
            {
                left--;
                right++;
                evenlength += 2;
            }
            if(evenlength > maxlength)
            {
                maxlength = evenlength;
            }
    
            ptag++;
        }
        return maxlength;
    }

原文链接：[点击打开链接1][1]       [点击打开链接2][2]

[1]: https://blog.csdn.net/duan19920101/article/details/51482244
[2]: https://www.cnblogs.com/heyonggang/p/3386724.html