neoevoke » [usaco] 1.3 Claf Flac

[usaco] 1.3 Claf Flac - usaco

2009.08.08 22:38 neoevoke Edit

시간 초과에 걸려서 한참 고생했던 문제이다.
20000자 까지 들어오는 문자열 안에서
가장 긴 Palindrome을 찾는 문제이다.
여러줄 입력 처리가 귀찮아서 /로 모두 엮은다음에
나중에 출력할 때는 /가 있으면 한줄 띄워주는 방식으로 처리하였다.

코딩이 좀 더러운데 개선의 여지가 있다고 본다.

/*
ID: neoevok1
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

bool upperdiff(char a, char b)
{
	if(!isalpha(a)) return false;
	if(!isalpha(b)) return false;
	if(a==b) return true;
	if(a>='a'&& a<='z')
		a='A'+(a-'a');
	else if(a>='A'&& a<='Z')
		a='a'+(a-'A');

if(a==b) return true;
	return false;
}

int main() {
    ofstream fout ("calfflac.out");
    ifstream fin ("calfflac.in");
	string ms;
	int m=1;
	string a;
	while(1)
	{
		string o;
		getline(fin, o);
		if(fin.eof()) break;
		a+=o+'/';
	}

int al=(int)a.length();
	int ml,mr;

for(int i=0;i<al;i++)
	{
		int l=i, r=i;
		int cnt=-1;
		while(l>=0 && !isalpha(a[l])) l--;
		while(r<al && !isalpha(a[r])) r++;
		if(l!=i) cnt=0;
		while(l>=0 && r<al && upperdiff(a[l],a[r]))
		{
			l--;
			r++;
			cnt+=2;
			while(l>=0 && !isalpha(a[l])) l--;
			while(r<al && !isalpha(a[r])) r++;
		}
		if(m<cnt)
		{
			m=cnt;
			ml=l;
			mr=r;
		}
		l=i, r=i+1;
		cnt=0;
		while(l>=0 && !isalpha(a[l])) l--;
		while(r<al && !isalpha(a[r])) r++;
		while(l>=0 && r<al && upperdiff(a[l],a[r]))
		{
			l--;
			r++;
			cnt+=2;
			while(l>=0 && !isalpha(a[l])) l--;
			while(r<al && !isalpha(a[r])) r++;
		}
		if(m<cnt)
		{
			m=cnt;
			ml=l;
			mr=r;
		}
	}

fout << m << endl;
	while(!isalpha(a[ml+1])) ml++;
	while(!isalpha(a[mr-1])) mr--;
	for(int i=ml+1;i<mr;i++)
	{
		if(a[i]!='/')
			fout << a[i];
		else
			fout << endl;
	}
	fout << endl;
	return 0;
}

[usaco] 1.3 Prime Cryptarithm [usaco] 1.3 Barn Repair

Trackbacks 0

엮인글 주소: http://dw.yutar.net/329390/f25/trackback

Comments 0

Leave Comments

neoevoke난 전설 같은건 믿지 않아

[usaco] 1.3 Claf Flac - usaco

Trackbacks 0

Comments 0

Leave Comments

Category

Recent Post

Recent Comment

Recent Trackback

Tag