解题思路

这道题目要求我们计算给定的摩尔斯电码序列可以被字典中的单词拆分成多少种不同的短语组合。关键在于如何高效地匹配摩尔斯序列和字典中的单词，并统计所有可能的拆分方式。

1. 预处理摩尔斯电码

首先，我们需要将字典中的每个单词转换为对应的摩尔斯电码。摩尔斯电码表中的每个字母对应一个固定的点和划的组合。例如，A对应.-，B对应-...，依此类推。我们可以预先存储这些摩尔斯编码，然后在处理字典时，将每个单词转换为对应的摩尔斯字符串。

2. 动态规划（DP）

动态规划是解决这个问题的核心方法。我们定义dp[i]表示前i个字符的摩尔斯序列可以被拆分的次数。初始化时，dp[0] = 1，表示空字符串有一种拆分方式（即不拆分）。

对于每个位置i，我们从i往前遍历所有可能的单词长度（最多是字典中最长单词的摩尔斯编码长度，这里假设最长为85），检查子串text[j+1...i]是否存在于字典中。如果存在，则dp[i] += dp[j] * mp[cur]，其中mp[cur]是当前子串在字典中出现的次数。

3. 优化

为了快速查找子串是否在字典中，我们使用一个哈希表（map<string, int>）来存储字典中所有单词的摩尔斯编码及其出现次数。这样可以在O(1)时间内判断子串是否存在。

4. 最终结果

遍历完整个摩尔斯序列后，dp[len]就是整个序列可以被拆分的次数，其中len是摩尔斯序列的长度。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <list>
#define LL long long
#define eps 1e-8
#define maxn 10010
#define mod 100000007
#define inf 0x3f3f3f3f3f3f3f3f
#define mid(a,b) ((a+b)>>1)
#define IN freopen("in.txt","r",stdin);
using namespace std;
 
string Morse[26] = {{".-"},{"-..."},{"-.-."},{"-.."},{"."},{"..-."},{"--."},
{"...."},{".."},{".---"},{"-.-"},{".-.."},{"--"},{"-."},{"---"},{".--."},
{"--.-"},{".-."},{"..."},{"-"},{"..-"},{"...-"},{".--"},{"-..-"},{"-.--"},{"--.."}
};
 
int n;
char text[maxn];
int dp[maxn];
map<string, int> mp;
 
int main(int argc, char const *argv[])
{
    //IN;
 
    int t; cin >> t;
    while(t--)
    {
        scanf("%s", text+1);
        scanf("%d", &n);
        mp.clear();
        for(int i=1; i<=n; i++) {
            char word[25];
            scanf("%s", word);
            string cur;
            for(int i=0; word[i]; i++) {
                cur += Morse[word[i] - 'A'];
            }
            mp[cur]++;
        }
 
        int len = strlen(text+1);
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(int i=1; i<=len; i++) {
            for(int j=max(0,i-85); j<i; j++) if(dp[j]){
                char cur[100] = {0};
                for(int k=j+1; k<=i; k++) {
                    cur[k-j-1] = text[k];
                }
 
                dp[i] += dp[j] * mp[cur];
            }
        }
 
        printf("%d\n", dp[len]);;
    }
 
    return 0;
}