algorithm - モールス符号の解析

Question

私はこの問題を解決しようとしています。目標は、与えられた単語の辞書でモールス文字列を解釈できる方法の数を決定することです。私がやったことは、最初に辞書の単語をモールス語に「翻訳」したことです。次に、単純なアルゴリズムを使用して、再帰的に解釈できるすべての方法を検索しました。

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <iterator>
using namespace std;

string morse_string;
int morse_string_size;
map<char, string> morse_table;
unsigned int sol;

void matches(int i, int factor, vector<string> &dictionary) {
    int suffix_length = morse_string_size-i;
    if (suffix_length <= 0) {
        sol += factor;
        return;
    }
    map<int, int> c;
    for (vector<string>::iterator it = dictionary.begin() ; it != dictionary.end() ; it++) {
        if (((*it).size() <= suffix_length) && (morse_string.substr(i, (*it).size()) == *it)) {
            if (c.find((*it).size()) == c.end())
                c[(*it).size()] = 0;
            else
                c[(*it).size()]++;
        }
    }

    for (map<int, int>::iterator it = c.begin() ; it != c.end() ; it++) {
        matches(i+it->first, factor*(it->second), dictionary);
    }
}

string encode_morse(string s) {
    string ret = "";
    for (unsigned int i = 0 ; i < s.length() ; ++i) {
        ret += morse_table[s[i]];
    }
    return ret;
}

int main() {
    morse_table['A'] = ".-"; morse_table['B'] = "-..."; morse_table['C'] = "-.-."; morse_table['D'] = "-.."; morse_table['E'] = "."; morse_table['F'] = "..-."; morse_table['G'] = "--."; morse_table['H'] = "...."; morse_table['I'] = ".."; morse_table['J'] = ".---"; morse_table['K'] = "-.-"; morse_table['L'] = ".-.."; morse_table['M'] = "--"; morse_table['N'] = "-."; morse_table['O'] = "---"; morse_table['P'] = ".--."; morse_table['Q'] = "--.-"; morse_table['R'] = ".-."; morse_table['S'] = "..."; morse_table['T'] = "-"; morse_table['U'] = "..-"; morse_table['V'] = "...-"; morse_table['W'] = ".--"; morse_table['X'] = "-..-"; morse_table['Y'] = "-.--"; morse_table['Z'] = "--..";
    int T, N;
    string tmp;
    vector<string> dictionary;
    cin >> T;

    while (T--) {
        morse_string = "";
        cin >> morse_string;
        morse_string_size = morse_string.size();
        cin >> N;
        for (int j = 0 ; j < N ; j++) {
            cin >> tmp;
            dictionary.push_back(encode_morse(tmp));
        }

        sol = 0;
        matches(0, 1, dictionary);
        cout << sol;

        if (T)
            cout << endl << endl;
    }

    return 0;
}

問題は、許可されている実行時間は 3 秒だけであり、アルゴリズムはこの制限時間内では機能しません。

これはこれを行う良い方法ですか?もしそうなら、何が欠けていますか? そうでなければ、良い戦略とは何かについてヒントをいただけますか?

EDIT : 辞書には最大で 10,000 語、モールス文字列には最大で 1,000 文字を含めることができます。