查找回文字符串

查找回文字符串

全栈程序员-站长 • 2022年6月5日下午10:16 • 未分类 • 阅读 29

大家好，又见面了，我是你们的朋友全栈君。

编写一个程序，寻找一篇英文文章中最长的回文字符串。

回文字符串是具有回文特性的字符串：即该字符串从左向右读，与从右向左读都一样。

输入文件不会超过500字符。这个文件可能一行或多行，但是每行都不超过80个字符（不包括最后的换行符）。在寻找回文时只考虑字母 ‘A’ – ‘Z’ 和 ‘a’ – ‘z’ ，忽略其他字符（例如：标点符号，空格等）。

输出的第一行应该包括找到的最长的回文的长度。下一行或几行应该包括这个回文的原文（没有除去标点符号，空格等），把这个回文输出到一行或多行（如果回文中包括换行符）。如果有多个回文长度都等于最大值，输出最前面出现的那一个。

测试输入：Confucius say: Madam, I’m Adam.
预期输出：
11
Madam, I’m Adam

#include <iostream>
#include<cstring>
using namespace std;

int main()
{ 
   
    int m=0;
    char str[500];
    while((str[m]=cin.get())!=EOF)
      m++;
    str[m]='\0';//输入字符数组
    int x=0,d=0,a[500];
    char s[500];//定义新的数组记录所提取的字符
    do
    { 
   
        if((str[x]>='a'&&str[x]<='z')||(str[x]>='A'&&str[x]<='Z'))
        { 
   
            s[d]=str[x];
            a[d]=x;
            d++;
        }
        x++;
    }while(str[x]!='\0');
    s[d]='\0';//提取原字符数组中英文字母
    int len = strlen(s);
    int start = 0;//回文字符串最前面的位置
    int maxlen = 0;//回文字符串最大长度
    int low;//回文字符位于中间位置前的字符位置
    int high;//回文字符位于中间位置后的字符位置
    for (int i=1;i<len;i++)//i表示回文字符串中间元素下标
    { 
   
        //回文字符串偶数长度
        low=i-1;
        high=i;
        while (low>=0&&high<len&&(s[low]==s[high])||(s[low]==(s[high]-32))||((s[low]-32)==s[high]))
        { 
   
            if ((high-low+1)>maxlen)
             { 
   
               maxlen=high-low+1;
               start=low;
             }
            low--;
            high++;
        }
    }
    for (int i=1;i<len;i++)
    { 
   
        //回文字符串奇数长度
        low=i-1;
        high=i+1;
        while (low>=0&&high<len&&(s[low]==s[high])||(s[low]==(s[high]-32))||((s[low]-32)==s[high]))
        { 
   
            if ((high-low+1)>maxlen)
            { 
   
                maxlen=high-low+1;
                start=low;
            }
            low--;
            high++;
        }
    }
    cout<<maxlen<<endl;
    for(int t=a[start];t<=a[start+maxlen-1];t++)
        cout<<str[t];//输出回文数组以及在原数组中其中间的字符
    return 0;