南郵OJ 1100最長回文子串

最長回文子列
時間制限(通常/Java):
1000 MS/3000 MS運転メモリ制限:65536 KByte
合計コミット:748テストに合格:242
試合の説明
文字列を入力し、その中の最大の返信サブ列を求めます.サブストリングの意味は、元のストリングに連続して現れる文字列フラグメントです.回文の意味は、abbaやyyyxyyのように、見ているのと逆さまに見ているのと同じです.判断するときは、すべての句読点とスペースを無視し、大文字と小文字を無視しますが、出力はそのままにします(文字列の先頭と末尾に余分な文字を出力しないでください).
入力
入力文字列の長さは5000を超えず、個別の行を占めます.
しゅつりょく
最も長い文字列を出力し、複数ある場合は出力開始位置が最も左になります.
サンプル入力
Confuciuss say: Madam,I?m Adam.
サンプル出力
Madam, I?m Adam
テーマソース
劉汝佳『アルゴリズムコンテスト入門経典』

#include<iostream>
#include<string>
#define MAX_N 5010
using namespace std;

int main(){
	int i,j,b,e,n,m,max;
	int pos[MAX_N];
	string str1,str2;

	getline(cin,str1);
	n = (int)str1.length();
	str2.resize(n);
	for(i=0,m=0; i<n; ++i){
		if(str1[i]>='a' && str1[i]<='z'){
			pos[m]=i;
			str2[m++]=str1[i];
		}else if(str1[i]>='A' && str1[i]<='Z'){
			pos[m]=i;
			str2[m++]=str1[i]-'A'+'a';
		}
	}
	b = 0;
	e = 0;
	max = 1;
	for(i=1;i<m;i++){
		for(j=1; i-j>=0 && i+j<m && str2[i+j]==str2[i-j]; j++);
		j--;
		if(max<2*j+1){
			max=2*j+1;
			b=i-j;
			e=i+j;
		}
		for(j=1; i-j>=0 && i-1+j<m && str2[i-j]==str2[i-1+j]; j++);
		j--;
		if(max<2*j){
			max=2*j;
			b=i-j;
			e=i-1+j;
		}
	}
	str1=str1.substr(pos[b],pos[e]-pos[b]+1);
	cout<<str1<<endl;
}