1780.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1780 on 2006-03-13 at 21:39:08 */ 
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

const int MAX = 10240;
const int L = 84;
const char MORSE[][5] = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..",
								"--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", 
								"-.--", "--.." };

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

int main()
{
	map<const char*, int, cmp> dict;
	char word[MAX][L], code[MAX];
	int dcd[MAX];
	int t, T, i, j;

	scanf("%d\n", &T);
	for(t = 0; t < T; t++) {
		memset(dcd, 0, sizeof(dcd)); dict.clear();
		int len = strlen(gets(code)), ml = 0, n;
		scanf("%d\n", &n);
		for(i = 0; i < n; i++) {
			char w[L]; gets(w); word[i][0] = 0;
			for(j = 0; w[j] != 0; j++) strcat(word[i], MORSE[w[j]-'A']);
			ml = max(ml, (int)strlen(word[i]));
			if(dict.count(word[i]) == 0) dict[word[i]] = 1;
			else dict.find(word[i])->second++;
		}
		dcd[len] = 1;
		for(i = len-1; i >= 0; i--) {
			char str[L] = { 0 }; int lmt = min(ml, len - i);
			for(j = 0; j < lmt; j++) {
				str[j] = code[i+j];
				if(dict.count(str) != 0) dcd[i] += dcd[i+j+1] * dict.find(str)->second;
			}
		}
		printf("%d\n", dcd[0]);
	}
	
	return 0;
}