直接暴力法,对每一个字母字符,向左向右略过所有非字母字符,判断遇到的两个字母是否相等,相等则更新一下以i为中心的回文串的最大长度。
回文串长度可能是奇数也可能是偶数,扫描两次即可。时间复杂度为O(2*10^4*10^3*2)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("calfflac.in");
ofstream fout("calfflac.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
char text[20000];
void solve()
{
int text_len = 0;
char ch;
while( in.get(ch) ){
text[text_len++] = ch;
}
int s,e;
int len;
s = e = len = 0;
//对每一个i,计算以i为中心的最长的回文
for(int i=0;i<text_len;++i){
if(!isalpha(text[i]) )
continue;
int pal_s,pal_e;
pal_s = i+1;
pal_e = i;
int pal_len = 0;
while(true){
pal_s--;
pal_e++;
while(pal_s>=0&&!isalpha(text[pal_s])){
pal_s--;
}
while(pal_e<text_len&&!isalpha(text[pal_e])){
pal_e++;
}
if(pal_s>=0&&pal_e<text_len&&toupper(text[pal_s])==toupper(text[pal_e])){
pal_len+=2;
if(pal_len>len){
len = pal_len;
s = pal_s;
e = pal_e;
}
}else{
break;
}
}
pal_s = i;
pal_e = i;
pal_len = 1;
while(true){
pal_s--;
pal_e++;
while(pal_s>=0&&!isalpha(text[pal_s])){
pal_s--;
}
while(pal_e<text_len&&!isalpha(text[pal_e])){
pal_e++;
}
if(pal_s>=0&&pal_e<text_len&&toupper(text[pal_s])==toupper(text[pal_e])){
pal_len+=2;
if((pal_len)>len){
len = pal_len;
s = pal_s;
e = pal_e;
}
}else{
break;
}
}
}
out<<len<<endl;
for(int i=s;i<=e;++i)
out.put(text[i]);
out<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}