h.cpp

ACM训练题解 最新版 共8题 ACM训练题解 最新版 共8题

// Problem H
// http://acm.uva.es/p/v109/10950.html
// Solution by semiconductor
#include <stdio.h>
#include <memory.h>
#include <string.h>
#define N 26
char code[N][4];
char have[N];
char text[1000];
char stack[1000];
int clen[N];
bool used[N];
void read(int n)
{
	int i,t;
	char buf[3];
	memset(used,false,sizeof(used));
	for(i=0;i<n;i++)
	{
		scanf("%s",buf);
		scanf("%s",code[buf[0]-'a']+1);
		used[buf[0]-'a']=true;
		code[buf[0]-'a'][0]='0';
		clen[buf[0]-'a']=strlen(code[buf[0]-'a'])-1;
	}
	for(i=t=0;i<N;i++)
		if(used[i])have[t++]='a'+i;

}
bool DFS(int pos,int len,int n,int top,int& cc)
{
	if(pos==len)
	{
		stack[top]='\0';
		printf("%s\n",stack);
		cc++;
		return cc==100;
	}
	int i;
	char t;
	for(i=0;i<n;i++)
	{
		t=have[i];stack[top]=t;
		if(clen[t-'a']<=len-pos&&memcmp(text+pos,code[t-'a']+1,sizeof(char)*clen[t-'a'])==0
			&&DFS(pos+clen[t-'a'],len,n,top+1,cc))
			return true;
		if(clen[t-'a']+1<=len-pos&&memcmp(text+pos,code[t-'a'],sizeof(char)*(1+clen[t-'a']))==0
			&&DFS(pos+clen[t-'a']+1,len,n,top+1,cc))
			return true;
	}
	return false;
}
int main()
{
	int n,cc,t=1;
	while(scanf("%d",&n),n)
	{
		read(n);
		scanf("%s",text);
		cc=0;
		printf("Case #%d\n",t++);
		DFS(0,strlen(text),n,0,cc);
		printf("\n");
	}
	return 0;
}