|
思路如下: 匹配的递归过程如下。 把单词和正文都转换成mos码来表示。 从正文的头部开始匹配。 如果某个单词是正文的前缀,那么从前缀后面的部分递归下去。 统计一下所有方案的数目,就是答案了。 子问题就是“从位置k开始匹配,有多少种方案”,数组保存即可。 关键在于怎样快速发现某个单词是正文的前缀。 如果顺序查找,复杂度O(N),超时。 如果枚举单词长度后二分查找,复杂度O(L*lgN),应该不会超时,但代码不太自然,比较难写。 如果枚举单词长度后用hash查找,复杂度O(L),不会超时,而且代码比较好写。 事实证明,经典的字符串hash函数同样可以用于mos码,在65536格的闭hash里面没有产生冲突!
#include <stdio.h> #include <string.h> #include <stdlib.h>
char *mos[] = { ".-", "-", "-.-.", "-..",
".", "..-.", "--.", ".",
"..", ".---", "-.-", ".-..",
"--", "-.", "---", ".--.",
"--.-", ".-.", "", "-",
"..-", "-", ".--", "-..-",
"-.--", "--..", };
#define HASH_SIZE 65536 #define INPUT_LEN 10032
struct _hash { int val, cnt; };
struct _hash hash[HASH_SIZE]; int dp[INPUT_LEN]; int max_len;
int strhash(char *str, int len) { int val; for (val = 0; len--; str++) val = val*31 + *str; return val & 0x7fffffff; }
struct _hash *find(int val) { int h;
for (h = val % HASH_SIZE; hash[h].cnt && hash[h].val != val; h = (h + 1) % HASH_SIZE ); return &hash[h]; }
void insert(char *str) { int len = strlen(str); int val = strhash(str, len); struct _hash *h = find(val);
// printf("insert %s\n", str);
if (len > max_len) max_len = len;
h->val = val; h->cnt++; }
int calc(char *str, int start) { struct _hash *h; int i, s;
// printf("start %d %s\n", start, str + start);
if (!str[start]) return 1;
if (dp[start] != -1) return dp[start];
s = 0; for (i = 1; str[start + i - 1] && i <= max_len; i++) { h = find(strhash(str + start, i)); // printf("len %d %s cnt %d\n", i, str + start, h->cnt); if (h->cnt) s += calc(str, start + i) * h->cnt; }
dp[start] = s; return s; }
void solve() { int i, j, d, n; static char word[32], str[256], in[10032];
memset(dp, -1, sizeof(dp)); memset(hash, 0, sizeof(hash)); scanf("%s%d", in, &n); for (i = 0; i < n; i++) { scanf("%s", word); str[0] = 0; for (j = 0; word[j]; j++) strcat(str, mos[word[j] - 'A']); insert(str); } // printf("max_len %d\n", max_len); printf("%d\n", calc(in, 0)); }
int main() { int d;
scanf("%d", &d); while (d--) solve();
return 0; }
|