Poj Solution 2564

http://poj.org/problem?id=2564

#include "stdio.h"
#include "string.h"
#include "vector"
using namespace std;

const int size = 25000;

vector< char* > s1[18][26];
vector< char* > s2[18][26];


char w[size][17];
int ans[size],len[size];

bool check( char *a, char *b )
{
    int la = len[ ( a - w[0] ) / 17 ],
        lb = len[ ( b - w[0] ) / 17 ];

    while( *a == *b )
        a++,b++;
    if( la >= lb ) a++;
    if( la <= lb ) b++;

    while( *a == *b && *b != '' )
        a++,b++;
    return *a == '' && *b == '';
}

int main()
{
    int i,j,l,t,h,k,answer=0,m;

    for( i=0; i<18; i++ )
    {
        for( j=0; j<26; j++ )
        {
            s1[i][j].clear();
            s2[i][j].clear();
        }
    }

    for( i=0; scanf( "%s", w[i] ) == 1 ; i++ )
    {
        l = len[i] = strlen( w[i] );
        ans[i] = 0;

        for( h = l-1; h <= l+1 ; h++ )
        {

            j = w[i][0] - 'a';
            m = s1[h][j].size();

            for( k=0; k<m; k++ )
            if( check( w[i], s1[h][j][k] ) && ( t = ans[ ( s1[h][j][k] - w[0] ) / 17 ] ) > ans[i] )
                ans[i] = t;
                        
            j = w[i][l-1] - 'a'; 
            m = s2[h][j].size();

            for( k=0; k<m; k++ )
            if( check( w[i], s2[h][j][k] ) && ( t = ans[ ( s2[h][j][k] - w[0] ) / 17 ] ) > ans[i] )
                ans[i] = t;
        
        }

        ans[i]++;

        s1[l][ w[i][0] - 'a' ].push_back( w[i] );
        s2[l][ w[i][l-1] - 'a' ].push_back( w[i] );
        
        if( ans[i] > answer )
            answer = ans[i];
    }

    printf( "%dn", answer );

    return 0;
}




											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *