# 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()
{

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] );