|
|
思路如下： 匹配的遞歸過(guò)程如下。 把單詞和正文都轉(zhuǎn)換成mos碼來(lái)表示。 從正文的頭部開(kāi)始匹配。 如果某個(gè)單詞是正文的前綴，那么從前綴后面的部分遞歸下去。 統(tǒng)計(jì)一下所有方案的數(shù)目，就是答案了。 子問(wèn)題就是“從位置k開(kāi)始匹配，有多少種方案”，數(shù)組保存即可。 關(guān)鍵在于怎樣快速發(fā)現(xiàn)某個(gè)單詞是正文的前綴。 如果順序查找，復(fù)雜度O(N)，超時(shí)。 如果枚舉單詞長(zhǎng)度后二分查找，復(fù)雜度O(L*lgN)，應(yīng)該不會(huì)超時(shí)，但代碼不太自然，比較難寫(xiě)。 如果枚舉單詞長(zhǎng)度后用hash查找，復(fù)雜度O(L)，不會(huì)超時(shí)，而且代碼比較好寫(xiě)。 事實(shí)證明，經(jīng)典的字符串hash函數(shù)同樣可以用于mos碼，在65536格的閉hash里面沒(méi)有產(chǎn)生沖突！
#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;
}
|