1733.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1733 on 2006-07-23 at 15:22:40 */ 
#include <cstdio>
#include <cstring>
#include <list>
using namespace std;

const int HASH_LIMIT = 49157;
const int MAX = 51200;
const int L_MAX = 128;
const char letter[] = "ijabcdefghklmnprstuvwxyoqz";
const char digit[] = "11222333445566777888999000";

class HashTable {
public:
	static int hash(const char*);
	list<int> table[HASH_LIMIT];
	void init();
};
int HashTable::hash(const char* str) {
	int i, l = (strlen(str)+1) / 2;
	unsigned int ret = 0;
	unsigned short *s = (unsigned short*)str;
	for (i = 0; i < l; i++) {
		ret ^= (s[i] << (i & 0x0F));
	}
	return ret % HASH_LIMIT;
}
void HashTable::init() {
	int i;
	for(i = 0; i < HASH_LIMIT; i++) {
		table[i].clear();
	}
}

class Word {
private:
	static char f[];
public:
	char spell[L_MAX/2];
	char num[L_MAX/2];
	static void init();
	void parse();
};
char Word::f[32];
void Word::init() {
	int i;
	for(i = 0; letter[i] != 0; i++) {
		f[letter[i]-'a'] = digit[i];
	}
}
void Word::parse() {
	char c;
	int l = 0;
	for(; (c = getchar()) != '\n'; c++) {
		if(c >= 'a' && c <= 'z') {
			spell[l] = c;
			num[l++] = f[c-'a'];
		}
	}
	spell[l] = num[l] = 0;
}

HashTable ht;
Word word[MAX];

int find(const char*, const int);

int main()
{
	
	int n, i, j, k;
	int min[L_MAX], next[L_MAX], order[L_MAX];
	char phone[L_MAX];

	Word::init();
	while(gets(phone) != NULL) {
		int len = strlen(phone);
		if(len == 0) {
			continue;
		}
		scanf("%d\n", &n);
		ht.init();
		for(i = 0; i < n; i++) {
			word[i].parse();
			int code = HashTable::hash(word[i].num);
			if(find(word[i].num, code) == -1) {
				ht.table[code].push_back(i);
			}
		}
		for(i = 0; i < len; i++) {
			min[i] = L_MAX;
		}
		min[len] = 0;
		for(i = len-1; i >= 0; i--) {
			for(j = i; j < len; j++) {
				if(min[j+1] != L_MAX) {
					char str[L_MAX] = {0};
					for(k = i; k <= j; k++) {
						str[k-i] = phone[k];
					}
					int code = HashTable::hash(str);
					int r = find(str, code);
					if(r != -1 && min[i] > min[j+1] + 1) {
						min[i] = min[j+1] + 1;
						order[i] = r;
						next[i] = j + 1;
					}
				}
			}
		}
		if(min[0] == L_MAX) {
			printf("0\nNosolution.");
		} else {
			printf("%d\n", min[0]);
			for(i = 0; i != len; i = next[i]) {
				printf("%s", word[order[i]].spell);
			}
		}
		putchar('\n');
	}
	
	return 0;
}

int find(const char* s, const int code)
{
	if(!ht.table[code].empty()) {
		list<int>::iterator it;
		for(it = ht.table[code].begin(); it != ht.table[code].end(); it++) {
			if(!strcmp(s, word[*it].num)) {
				return *it;
			}
		}
	}
	return -1;
}