|
|
思路如下： 匹配的递归过程如下。 把单词和正文都转换成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;
}
|