D1. Prefix-Suffix Palindrome (Easy version)
발상을 못떠올려서 못 푼 문제입니다.
설계를 못한거죠.
hard 버전도 같은 방법인데, 시간복잡도를 줄이기 위해 manacher's algorithm이란 것만 추가로 이용하면 됩니다.

rating : 1500
tags : hashing ,string suffix structures ,strings

문제

문자열 s가 주어집니다. s의 prefix와 suffix를 붙여서 문자열 t를 만듭니다. t는 팰린드롬이어야 합니다. 가장 긴 t를 구하는 것이 문제입니다. 길이가 같은 것이 여러개 있으면 아무거나 출력합니다.

어려움

연산량(시간복잡도)

제한은 모든 테스트 케이스를 다 합쳐서 s의 길이 < 5000입니다. 아주 naive한 방법으로 하면 n^3입니다. 시간제한을 통과하지 못합니다. 그런데 이 방법 말고는 어떻게 해야할지 생각이 안났습니다.

해결

해법은 간단합니다. 그런데 이 방법은 전혀 생각도 못했습니다.

1. prefix와 suffix에서 같은 문자들로 최대한 팰린드롬을 만듭니다.
2. 남은 가운데 문자열에서 아래의 둘 중 긴 문자열을 가운데 끼워넣으면 됩니다.
   1) prefix 문자열 중에 가장 긴 팰린드롬 문자열
   2) suffix 문자열 중에 가장 긴 팰린드로 문자열

int main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	int tc; cin>>tc;
	while(tc--){
		//아 모르겠다..
		string s; cin>>s;
		int l=0,r=s.size()-1;
		string ansleft="",ansright="";
		for(;l<r && s[l]==s[r];l++,r--){
			ansleft+=s[l];
			ansright=s[r]+ansright;
		} 
		if(l>r) {
			cout<<ansleft+ansright<<"\n";
			continue;
		}
		
		
		string maxmid="";
		for(int i=l;i<=r;i++){
			int l2=l,r2=i;
			bool possible=true;
			for(;l2<r2;l2++,r2--){
				if(s[l2]!=s[r2]) {
					possible=false;
					break;
				}
			}
			if(possible){
				if(maxmid.size()<i-l+1){
					maxmid=s.substr(l,i-l+1);
				}
//				cout<<" "<<i<<" "<<maxmid<<"\n";
			}
		}
		
		string maxmid2="";
		for(int i=l;i<=r;i++){
			int l2=i,r2=r;
			bool possible=true;
			for(;l2<r2;l2++,r2--){
				if(s[l2]!=s[r2]) {
					possible=false;
					break;
				}
			}
			if(possible){
				if(maxmid2.size()<r-i+1){
					maxmid2=s.substr(i,r-i+1);
				}
//				cout<<" "<<i<<" "<<maxmid2<<"\n";
			}
		}
		
		if(maxmid2.size() > maxmid.size()) maxmid=maxmid2;
		
//		cout<<ansleft<<"\n";
		
		cout<<ansleft+maxmid+ansright<<"\n";
	}
}