[USACO] 1.3 Calf Flac(Winning Solutions)

시간 제약조건때문에 계속 실패가 났다.
처음 시도한 방법은 n까지 돌면서, 2000부터 역으로 돌면서 펠린드롬인 경우 크기를 리턴하게 하면서,
나머지 경우에 대해 2000부터 현재 구한 값까지 펠린드롬인지 계산했다.
이 방법으로 1~7번 입력까지는 만족했으나, 계속 8번 입력이 1.5초를 초과했다.

결국 수정한 알고리즘은 n까지 돌면서, n을 중심으로 한 최대 펠린드롬의 크기를 구하는 방법.

앞의 방법이 n* 2000에 대해 펠린드롬을 계산하는데 반해 뒤의 방법은 n에 대해 펠린드롬을 계산한다.
즉, O(n*2000*펠린드롬계산)과 O(n*2*펠린드롬계산)의 차이로 볼 수 있겠다..


int check_pal(char d[], int start, int end, int n)
{
    int ret = 0;
    while(start >= 0 && end - start <= 2000 && end < n)
    {       
        if( !isalpha(d[start]) ) start--;
        else if( !isalpha(d[end]) ) end++;
        else if( tolower(d[start]) != tolower(d[end]) ) return ret;
        else
        {
            if( start == end) ret++;
            else ret += 2;

            start--;
            end++;
        }
    }
    return ret;
}

int main() {

    ofstream fout ("calfflac.out");
    ifstream fin ("calfflac.in");
   
    char data[20000];
    char c;
    int n = 0;
    while(fin.good())
    {
        c = fin.get();
        data[n] = c;
        n++;
    }
   
    int ret = 0, sum = 0;
    REP(i, n)
    {
        int start = i;
        int end = i;
        int m1 = check_pal(data, start, end, n);
        if( sum < m1 )
        {
            sum = m1;
            ret = i;
        }

        end = i+1;
        int m2 = check_pal(data, start, end, n);
        if( sum < m2)
        {
            sum = m2;
            ret = i;
        }
    }

    fout << sum  << endl;

    int cnt = sum / 2;
    int start, end;

    int ret2 = ret;
    if( sum % 2 == 1) ret2--;
    int count = cnt;
    for( int i= ret2; i >= 0; i--)
    {
        if( isalpha(data[i]) ) count--;
        if(count == 0)
        {
            start = i;
            break;
        }
    }

    count = cnt;
    for( int i= ret+1; i < n; i++)
    {
        if( isalpha(data[i]) ) count--;
        if(count == 0)
        {
            end = i;
            break;
        }
    }

    for(int i= start; i <= end; i++)
        fout << data[i];
    fout << endl;

    return 0;
}