e.cpp

ACM大赛基本练习题

#include<stdio.h>
#include<string.h>

#define MAXN 15
#define MAXLEN 25
#define MAXST 110

int n;

char *word[MAXN];
char wordst[MAXN][MAXLEN];
char st[MAXST];

void read_dat()
{
	int i;

	scanf( "%d", &n );
	for( i = 0; i < n; ++i )
	{
		scanf( "%s", wordst[i] );
		word[i] = wordst[i];
	}
	scanf( "%s", st );
}

void swap_it( int n1, int n2 )
{
	char *tmp = word[n1];
	word[n1] = word[n2];
	word[n2] = tmp;
}

void sort_it( int s, int t )
{
	int now = s, i;

	if( s >= t )
		return;

	swap_it( s, ( s + t ) / 2 );

	for( i = s + 1; i <= t; ++i )
		if( strcmp( word[i], word[s] ) < 0 )
			swap_it( i, ++now );
	swap_it( s, now );
	sort_it( s, now - 1 );
	sort_it( now + 1, t );
}

int find_it( int *s, int *t, int pos, char ch )
{
	int nows = *s, nowt;
	while( nows <= *t && word[nows][pos] < ch )
		++nows;
	if( nows > *t || word[nows][pos] != ch )
		return 0;
	nowt = nows + 1;
	while( nowt <= *t && word[nowt][pos] == ch )
		++nowt;
	*s = nows;
	*t = nowt - 1;
	return 1;
}

void make_it()
{
	char *ch;
	int s = 0, t = n - 1;
	int pos = 0;

	for( ch = st; *ch; ++ch )
	{
		if( *ch == '#' )
		{
			if( pos != 0 )
				printf( "%s\n", word[s] );
			s = 0;
			t = n - 1;
			pos = 0;
		}
		else if( find_it( &s, &t, pos, *ch ) )
			pos++;
	}
}

int main()
{
	int i, dataCase;

	scanf( "%d", &dataCase );
	
	for( i = 0; i < dataCase; ++i )
	{
		read_dat();
		sort_it( 0, n - 1 );
		make_it();
	}

	return 0;
}