2564.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2564  User Id:fzk 
Memory:948K  Time:2046MS
Language:C++  Result:Accepted

Source 

#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 != '\0' )
		a++,b++;
	return *a == '\0' && *b == '\0';
}

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( "%d\n", answer );

	return 0;
}