最长回文子串（2013华科机试）

左手的ㄟ右手 2022-05-30 06:27 135阅读 0赞

最长子回文串(40 分)、 输入一个字符串，求出其中最长的回文子串。子串的含义是:在原串连续出现的字符串片段。 回文的含义是:正着看和倒着看是相同的，如 abba 和 abbebba。在判断是要求忽略所有的 标点和空格，且忽略大小写，但输出时按原样输出(首尾不要输出多余的字符串)。输入字 符串长度大于等于 1 小于等于 5000  
样例输入  
She say:Madam,I’m Adam.  
样例输出 Madam,I’m Adam

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    
    int is_letter(char a){
        if((a >= 'a' && a <= 'z' )|| (a >= 'A' && a <= 'Z')) return 1;
        else return 0;
    }
    
    char upper(char a){
        if(is_letter(a)){
            if(a >= 'a' && a <= 'z') return a = a + 'A' - 'a';
            else return a;
        }
        else return a;
    }
    
    int main(){
        int low,high;
        char string[5001];
        char position[5001];
        char hstring[5001];
        int index = 0;
        int maxlen = -1;
        while(gets(string) != NULL){
            int len = strlen(string);
            for(int i = 0;i < len;i ++){
                if(is_letter(string[i])){
                    char up_letter = upper(string[i]);
                    hstring[index] = up_letter;
                    position[index] = i;
                    index ++;
                }
            }
            for(int i = 0;i < index;i ++){
                for(int j = 0;i - j >=0 && i + j < index;j ++){
                    if(hstring[i - j] != hstring[i + j]) break;
                    else if(2 * j + 1 > maxlen){
                        maxlen = 2 * j + 1;
                        low = position[i - j];
                        high = position[i + j];
                    }
                }
            }
            for(int i = 0;i < index;i ++){
                for(int j = 0;i - j >= 0 && i + j + 1 < index;j ++){
                    if(hstring[i - j] != hstring[i + j + 1]) break;
                    else if(2 * j + 2 > maxlen){
                        maxlen = 2 * j + 2;
                        low = position[i - j];
                        high = position[i + j + 1];
                    }
                }
            }
            for(int i = low;i <= high;i ++) printf("%c",string[i]);
            printf("\n");
        }
        return 0;
    }