2004.txt

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

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

#define MAXN 16384
#define MAXST 32
#define NHASH 10001
#define MUL 37

class Node
{
public:
	char *st;
	char *frm;
	int len;
	int max;
	Node *next;
	Node *pre;
};

char st[MAXN][MAXST];
char frm[MAXN][MAXST];
Node *tab[2][NHASH];
Node rec[MAXN];
Node *pt[MAXN];
int n;

int cmp( const void *n1, const void *n2 )
{
	return ( *( Node ** ) n1 )->len - ( *( Node ** ) n2 )->len;	
}

void read_it()
{
	n = 0;
	while( scanf( "%s", st[n] ) != EOF )
	  ++n;
	for( int i = 0; i < n; ++i )
	{
		rec[i].frm = st[i];
		strcpy( frm[i], st[i] );
		rec[i].st = frm[i];
		rec[i].len = strlen( st[i] );
		for( int j = 0; j < rec[i].len; ++j )
		  for( int k = j + 1; k < rec[i].len; ++k )
		    if( frm[i][j] > frm[i][k] )
		    {
		    	char ch = frm[i][j];
		    	frm[i][j] = frm[i][k];
		    	frm[i][k] = ch;
		    }
		pt[i] = &rec[i];
	}
	qsort( pt, n, sizeof( pt[0] ), cmp );
}

unsigned geth( char *st )
{
	unsigned h = 0;
	for( char *ch = st; *ch; ++ch )
	  h = h * MUL + ( *ch );
	return h % NHASH;
}

void add_it( Node *tab[], Node *now )
{
	unsigned h = geth( now->st );
	now->next = tab[h];
	tab[h] = now;
}

Node *find_it( Node *tab[], char *st )
{
	unsigned h = geth( st );
	for( Node *now = tab[h]; now; now = now -> next )
	  if( strcmp( now->st, st ) == 0 )
	    return now;
	return NULL;
}

void make_it()
{
	int i, j, pre = 0, now = 1, k, p;
	memset( tab[pre], 0, sizeof( tab[pre] ) );
	for( i = 0; i < n && pt[i]->len == pt[0]->len; ++i )
	{
		add_it( tab[pre], pt[i] );
		pt[i]->pre = NULL;
		pt[i]->max = 1;
	}
	char tmp[MAXST];
	for( ; i < n; )
	{
		memset( tab[now], 0, sizeof( tab[now] ) );
		for( j = i; j < n && pt[j]->len == pt[i]->len; ++j )
		{
			add_it( tab[now], pt[j] );
			pt[j]->max = 0;
			strcpy( tmp, pt[j]->st );
			for( k = pt[j]->len - 1; k >= 0; --k )
			{
				tmp[k] = pt[j]->st[k + 1];
				Node *nod = find_it( tab[pre], tmp );
				if( nod && nod->max > pt[j]->max )
				{
					pt[j]->max = nod->max;
					pt[j]->pre = nod;
				}
			}
			++pt[j]->max;
		}
		i = j;
		pre = now;
		now = 1 - now;
	}
}

void put_it( Node *now )
{
	if( now == NULL )
	  return;
	put_it( now->pre );
	printf( "%s\n", now->frm );
}

void get_result()
{
	int nowmax = 0;
	Node *now;
	for( int i = 0; i < n; ++i )
	  if( pt[i]->max > nowmax )
	  {
	  	nowmax = pt[i]->max;
	  	now = pt[i];
	  }
	put_it( now );
}

int main()
{
	read_it();
	make_it();
	get_result();
	return 0;
}