1

我正在尝试解决这个问题。目标是在给定字典的情况下确定可以解释莫尔斯字符串的方式数量。我所做的是我首先将字典中的单词“翻译”成莫尔斯语。然后，我使用了一种朴素的算法，寻找可以递归解释它的所有方式。

#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 秒的执行时间，而我的算法在这个时间限制下将无法工作。

这是做到这一点的好方法吗？如果是这样，我错过了什么？否则，您能否提供一些关于什么是好的策略的提示？

编辑：字典中最多可以有 10 000 个单词，莫尔斯字符串中最多可以有 1000 个字符。

4

1 回答 1

0

将动态编程与滚动哈希相结合的解决方案应该可以解决这个问题。

让我们从一个简单的动态规划解决方案开始。我们分配一个向量，我们将使用它来存储前缀的已知计数morse_string。然后我们遍历morse_string并在每个位置遍历所有单词，然后回头看看它们是否适合morse_string. morse_string如果它们可以拟合，那么我们使用动态规划向量来确定我们可以建立多少种方式的前缀i-dictionaryWord.size()

vector<long>dp;
dp.push_back(1);
for (int i=0;i<morse_string.size();i++) {
   long count = 0;
   for (int j=1;j<dictionary.size();j++) {
       if (dictionary[j].size() > i) continue;
       if (dictionary[j] == morse_string.substring(i-dictionary[j].size(),i)) {
           count += dp[i-dictionary[j].size()];
       }
   }
   dp.push_back(count);
}
result = dp[morse_code.size()]

这个解决方案的问题是它太慢了。假设N是长度，morse_string是M字典的大小dictionary，K是字典中最大单词的大小。它将进行O(N*M*K)操作。如果我们假设K=1000这是关于10^10大多数机器上太慢的操作。

K成本来自生产线dictionary[j] == morse_string.substring(i-dictionary[j].size(),i)

如果我们可以加速这个字符串匹配到常量或日志复杂度，我们就可以了。这就是滚动哈希的用武之地。如果您构建一个滚动哈希数组，morse_string那么您可以计算 in 的任何子字符串的morse_string哈希O(1)。所以你可以这样做hash(dictionary[j]) == hash(morse_string.substring(i-dictionary[j].size(),i))

这很好，但在存在不完美哈希的情况下，您可能会从字典中获得多个具有相同哈希的单词。这意味着在获得哈希匹配后，您仍然需要匹配字符串和哈希。在编程竞赛中，人们经常假设完美的散列并跳过字符串匹配。这通常是一个安全的赌注，尤其是在一本小字典上。如果它没有产生完美的散列（你可以在代码中检查），你总是可以稍微调整你的散列函数，也许调整后的散列函数会产生一个完美的散列。

于 2014-05-15T12:38:42.190 回答