#include<iostream>
#include<fstream>
using namespace std;

#define KEY_MAX 9
#define WORD_MAX 1000
char* wordstrs[WORD_MAX]={0};
int indexofchar['z'-'a'+1];

struct word
{
	char * str;
	int weight;
	word():str(0),weight(0) {}
};

class numnode
{
	char* _prev;
	char* _next;
	int _weight_next;
	int _weight_prev;
	numnode* _childs[KEY_MAX];
	int _end;//end of word str index

public:
	numnode():_weight_next(0),_weight_prev(0),_prev(0),_next(0),_end(0) { for(int i=KEY_MAX-1;i>=0;--i){ this->_childs[i]=0;} }

	~numnode() 
	{
		if(this->_childs)
		{
			for(int i=KEY_MAX-1;i>=0;--i)
				if(this->_childs[i])
					delete this->_childs[i]; 
		}
	}

	void putword(word& wo,int at)
	{
		int i;
		if(at)
		{
			if(at==2&&wo.str[at-2]=='f'&&wo.str[at-1]=='i')
				cout<<'g';
			if(this->_prev)
			{
				for(i=0;i<at;++i)
				{
					if(this->_prev[i]!=wo.str[i]) break;
				}
				if(i==at)
				{
					//wo.weight+=this->_weight_prev;
					this->_weight_prev+=wo.weight;
				}
				else
				{
					i=0;
					if(this->_next)
					{
						for(;i<at;++i)
						{
							if(this->_next[i]!=wo.str[i]) break;
						}
					}
					if(i==at)
					{
						//wo.weight+=this->_weight_next;
						this->_weight_next+=wo.weight;
						if(this->_weight_next>this->_weight_prev)
						{
							this->_prev=this->_next;
							this->_weight_prev=this->_weight_next;
							this->_end=at;
							this->_next=0;
						}
					}
					else
					{
						if(wo.weight>this->_weight_prev)
						{
							this->_prev=wo.str;
							this->_weight_prev=wo.weight;
							this->_next=0;
							this->_end=at;
						}
						else
						{
							this->_next=wo.str;
							this->_weight_next=wo.weight;
						}
					}
				}
			}
			else
			{
				this->_prev=wo.str;
				this->_weight_prev=wo.weight;
				this->_end=at;
			}
		}
		if(wo.str[at])
		{
			int index=indexofchar[wo.str[at]-'a'];
			if(!(this->_childs[index])) this->_childs[index]=new numnode();
			this->_childs[index]->putword(wo,at+1);
		}
	}
	numnode* next(int num)
	{
		return this->_childs[num-1];
	}

	void output(ostream& out)
	{
		for(int i=0;i<this->_end;++i) out<<this->_prev[i];
	}
};

void init()
{
	int i=0;
	while(i<'d'-'a') indexofchar[i++]=1;
	while(i<'g'-'a') indexofchar[i++]=2;
	while(i<'j'-'a') indexofchar[i++]=3;
	while(i<'m'-'a') indexofchar[i++]=4;
	while(i<'p'-'a') indexofchar[i++]=5;
	while(i<'t'-'a') indexofchar[i++]=6;
	while(i<'w'-'a') indexofchar[i++]=7;
	while(i<'z'-'a') indexofchar[i++]=8;
	indexofchar[i]=8;
}

void deal(istream&fin,ostream&fout)
{
	int i,j,m,n;
	char ch;
	numnode* mainnode;
	numnode* prevnode;
	char wordinput[102];
	word oneword;
	int times,go;
	fin>>times;
	init();
	for(go=1;go<=times;++go)
	{
		mainnode=new numnode();
		fin>>m;
		for(n=m-1;n>=0;--n)
		{
			fin>>wordinput;
			i=0;
			while(wordinput[i++]);
			oneword.str=new char[i];
			wordstrs[n]=oneword.str;
			for(--i;i>=0;--i) oneword.str[i]=wordinput[i];
			fin>>oneword.weight;
			mainnode->putword(oneword,0);
		}
		fout<<"Scenario #"<<go<<':'<<endl;
		fin>>j;
		for(--j;j>=0;--j)
		{
			prevnode=mainnode;
			while(fin>>ch&&ch>'1') 
			{
				if(prevnode) prevnode=prevnode->next(ch-'0');
				if(prevnode) prevnode->output(fout);
				else fout<<"MANUALLY";
				fout<<endl;
			}
			fout<<endl;
		}
		fout<<endl;
		for(--m;m>=0;--m)
		{
			if(wordstrs[m])
			{
				delete wordstrs[m];
				wordstrs[m]=0;
			}
		}
		delete mainnode;
	}
}

int main()
{
	deal(cin,cout);
	return 0;
}

• Re:无尽的WA (16) lynfince 2007-07-22 08:28:32