求给定字符串中最长的回文串什么,要求输出的是原来文章中的字符串。我们可以将字符串预处理,删除掉多余的字符,并记录每个字符的位置

然后开始枚举回文串。从第i个字符开始,分别判断(i-1,i+1)和(i,i+1)开始的字符串向两边不断的延伸。。记录位置即可

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int INF = 0x7f7f7f7f;
char s[20010];
struct td
{
    char c;
    int loc;
} str[21000];
int cnt,n,maxx=0;
int low,high;
void judge(int l,int r)
{
    while(l>=0&&r<cnt)
    {
        if(str[l].c==str[r].c)
        {
            l--;
            r++;
        }
        else
            break;
    }
    if(r-l-1>maxx)
    {
        maxx=r-l-1;
        low=l+1;
        high=r-1;
    }
}
int main()
{
    char c;
    int i;
    cnt=0,n=0;
    memset(str,0,sizeof(str));
    low=high=0;
    while((c=getchar())!=EOF)
        s[n++]=c;
    s[n]=0;
    for(i=0; i<n; i++)
    {
        if(!((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')))
            continue;
        if(s[i]>='A'&&s[i]<='Z')
            c=s[i]-'A'+'a';
        else
            c=s[i];
        str[cnt].c=c;
        str[cnt++].loc=i;
    }
    /*for(i=0;i<cnt;i++)
        cout<<str[i].c;*/
    for(i=0; i<cnt; i++)
    {
        judge(i-1,i+1);
        judge(i,i+1);
    }
    printf("%d\n",maxx);
    if(maxx)
    {
        for(i=str[low].loc; i<=str[high].loc; i++)
            printf("%c",s[i]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation