基础算法：最大回文长度

待我称王封你为后i 2022-12-19 00:57 126阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]

这篇文章介绍一下最大回文字符串长度的一种计算方法。

### 目录 ###

*  什么是回文
 *  问题说明
 *  解题思路
 *  示例代码
 *  执行示例
 *  总结

--------------------

# 什么是回文 #

从左向右念和从右向左念一样：上海自来水来自海上。比如英文字符aba或者abba。

# 问题说明 #

在一个字符串中，如果包含回文字符串，请确认其可能的最大长度是多少。

# 解题思路 #

除去常规的套路，这篇文章分享一种简单的实现方式，具体思路如下：

*  回文分为aba或者abba两种类型
 *  回文的计算主要分为两层循环，具体方式有两种：按aba的方式，左移指针和右移指针重叠；按abba的方式，左移指针 + 1 == 右移指针。内层循环中分别左右移位，如果各移动一位之后仍然相等，则继续移动，这个过程中不断更新回文的长度，整个循环的的aba和abba最大值即为题解。

# 示例代码 #

int palindrome(char* str, int left, int right) { 
        int palindrome_length = 0;
        int string_length = strlen(str);
        
        while(left >=0 && right <string_length && str[left]==str[right]) { 
            palindrome_length = right - left + 1;
            left--; right++;
        }
        
        return palindrome_length;
    }
    
    int max_palindrome_len(char* str) { 
        int string_length = strlen(str);
        int max_len = 0;
        for (int i=0; i<string_length; i++) { 
            int aba_len=palindrome(str,i,i);
            int abba_len=palindrome(str,i,i+1);
            
            max_len=max_len>aba_len?max_len:aba_len;
            max_len=max_len>abba_len?max_len:abba_len;
        }
        return max_len;
    }

--------------------

# 执行示例 #

#include <stdio.h>
    #include <string.h>
    
    #define MAX_STRING_LENGTH 3000
    
    int palindrome(char* str, int left, int right) { 
        int palindrome_length = 0;
        int string_length = strlen(str);
        
        while(left >=0 && right <string_length && str[left]==str[right]) { 
            palindrome_length = right - left + 1;
            left--; right++;
        }
        
        return palindrome_length;
    }
    
    int max_palindrome_len(char* str) { 
        int string_length = strlen(str);
        int max_len = 0;
        for (int i=0; i<string_length; i++) { 
            int aba_len=palindrome(str,i,i);
            int abba_len=palindrome(str,i,i+1);
            
            max_len=max_len>aba_len?max_len:aba_len;
            max_len=max_len>abba_len?max_len:abba_len;
        }
        return max_len;
    }
    int main() { 
        char str_info[MAX_STRING_LENGTH] = {  0 };
        while(scanf("%s",&str_info) != EOF) { 
            printf("%d\n",max_palindrome_len(str_info));
        }
        return 0;
    }

# 总结 #

这篇文章介绍了回文长度的计算方式。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/88fbbec14046481f895f13e63946f0de.png