题目大意:
给出一个字符串(可能有多行),在只考虑字母的情况下(忽略大小写)找出一个最长的回文序列。
思路:
在程序最开始需要对数据进行预处理,提取字符串中的所有字母再全部转换为小写并存入进结构体序列tmp[]中,tmp[i].t表示字符串中第i个字母的小写形式。完成此题目需要动态规划的思想,分成两种情况考虑:
找出最长的奇数回文序列。需要用到一个辅助数组length[]。当tmp[i-length[i]-1].t==tmp[i+1].t时,length[i+1]=length[i]+2。
找出最长的偶数回文序列。同样用到辅助数组length[]。当tmp[i-length[i]].t==tmp[i+1].t时,length[i+1]=length[i]+2。
代码:
/* ID: lujunda1 LANG: C++ PROG: calfflac */ #include<iostream> #include<stdio.h> #include<cstring> #include<cstdio> #include<stdlib.h> using namespace std; //words用来存储输入的原始数据 //tmp_words是在处理多行输入时用到的辅助数组 char words[20001],tmp_words[20001]; //计算前需要对原始数据进行处理,仅保留字母(全部转换为小写)并记录每个字母在原始数据中的位置。 struct point { char t; int pos; }tmp[20001]; //length数组用于记录当前位置所属回文序列的最大长度(实际因回文数列长度的奇偶性而有所差异) int length[20001]; //多行输入 void input() { words[0]='\0'; while(gets(tmp_words)) { int len=strlen(words); //如果words长度不为0,则说明现在输入的不是第一行数据。 if(len) { //输入前,将“上一行”结尾的‘\0’改为‘\n’。 words[len]='\n'; strcpy(words+len+1,tmp_words); } //如果words的长度为0,则说明现在正在输入第一行数据。 else strcpy(words,tmp_words); } } int main() { freopen("calfflac.in","r",stdin); freopen("calfflac.out","w",stdout); input(); //len用于记录处理过后的数据的长度。(所有字母的个数) int len=0; for(int i=0,tmp_len=strlen(words);i<tmp_len;i++) if(words[i]>='a'&&words[i]<='z') { tmp[len].pos=i; tmp[len++].t=words[i]; } else if(words[i]>='A'&&words[i]<='Z') { tmp[len].pos=i; tmp[len++].t=words[i]-'A'+'a'; } //下面代码是找出最大的奇数回文序列。 //max_1表示最大的奇数回文序列长度 //pos_1表示最大的奇数回文序列的最后一个字母所在位置 int max_1=0,pos_1=0; memset(length,0,sizeof(length)); for(int i=0;i<len;i++) { //start、end分别表示与当前最大奇数回文序列相邻的左右两个字母的位置。 int start=i-length[i]-1,end=i+1; if(start>=0&&end<len&&tmp[start].t==tmp[end].t) //这里需要注意,length[i]表示的是当前“最大奇数回文序列的长度-1” length[i+1]=length[i]+2; //不断更新max_1和pos_1的值 if(max_1<length[i]) { max_1=length[i]; pos_1=i; } } //由length的性质可知,max_1实际是最大长度-1。为了使max_1表示最大长度,这里需要加1。 max_1++; //下面代码是找出最大偶数回文序列。 //max_2与pos_2的含义与之前类似。 int max_2=0,pos_2=0; memset(length,0,sizeof(length)); for(int i=0;i<len;i++) { //start与end的含义也与上面类似。但当i等于0时,start==i,start在当前回文序列中。 int start=i-length[i],end=i+1; if(start>=0&&end<len&&tmp[start].t==tmp[end].t) //这里需要注意,length表示当前“最大偶数回文序列的长度” length[i+1]=length[i]+2; if(max_2<length[i]) { max_2=length[i]; pos_2=i; } } //max和pos分别表示最大回文序列的长度和最后一个字母的位置。 int max=max_1>max_2?max_1:max_2,pos=max_1>max_2?pos=pos_1:pos_2; printf("%d\n",max); for(int i=tmp[pos-max+1].pos;i<=tmp[pos].pos;i++) printf("%c",words[i]); printf("\n"); }