2

我有两个单独的单词数组，例如：

array1 = word1, word2, word3
array2 = word4, word5, word6

我正在尝试根据用户输入（将是 2 个单词）匹配这两个数组。例如，你输入“word1 word6”，程序给你 x。您输入“word3 word4”，程序会为您提供 y。每个数组中不需要/不应该匹配（因此输入“word1 word3”不应该给出错误以外的任何内容）。

现在，我正在考虑使用string::find在输入字符串中查找每个数组的内容。但是，在那之后，我一直坚持如何获取这些结果（如果有的话）并将它们相互匹配。

例如，我会input.find(contents of array1)，如果找到了某些东西，就拿那个array1[x]，看看array2[x]通过同一输入中的单独行找到的组合是否与第三个可能组合列表匹配。如果是这样，我会根据它是哪个组合来拆分响应。

我知道如果我只有一个可能匹配的列表并在输入字符串中找到它会更容易。但我想将这两组单词分开，因为代码会更灵活（我会通过这种方式学到更多）。

希望有人可以给我一些关于如何进行的提示？

4

4 回答 4

5

C++ 对这类问题有一个特殊的结构，叫做“map”

typedef std::map< std::pair< std::string, std:: string >, int > MyMapType;
MyMapType my_map;

例如，上面是一个给定一对字符串的映射返回一个 int。当然，并非所有可能的字符串对都需要包含在映射中：

my_map[std::make_pair("A", "B")] = 42;
my_map[std::make_pair("A", "C")] = 99;
my_map[std::make_pair("B", "D")] = 103;

要查看是否存在特定对，您可以使用map::find：

MyMapType::iterator i = my_map.find(std::make_pair(x, y));
if (i == my_map.end()) {
    std::cout << "Pair is not defined\n";
} else {
    // Pair is present
    std::cout << "Associated value is " << *i << "\n";
}
于 2013-09-24T07:27:17.313 回答
1

最简单的选择不是使用std::set_intersection来获取公共元素。不过，您确实需要排序的输入。

  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};

  it=std::set_intersection (first, first+5, second, second+5, v.begin());

将产生一个包含 20 个元素的向量：10 和 20。（根据链接）。

于 2013-09-24T08:29:02.170 回答
0
据我了解：
  • 你有两组词，
  • 来自用户的 2 个单词和
  • 你想知道这两个词是否包含在这些集合中，但不是来自同一个集合

然后你可能会做类似的事情：

inline const bool isIn(const std::set<std::word>& s, const std::string& e) {
    return s.find(e) != s.end();
}

...

std::set<std::string> wordSet1, wordSet2;
std::string word1, word2; // <-- from the user
...
if (isIn(wordSet1, word1) && isIn(wordSet2, word2)) {
    // success
}
else if (isIn(wordSet2, word1) && isIn(wordSet1, word2) {
    // success
}
else {
    // fail
}

但由于复杂度std::set::find是 O(log n) 并且这种方法调用了 4 次，所以它不是很有效。另请注意，如果 order 定义明确，即word1must be fromwordSet1且word2must be from ，则应省略wordSet2第二个条件 ( )。else if

如果顺序定义明确并且您需要多次查找这些对，那么创建一个std::set< std::pair<std::string, std::string> >包含所有可能组合的临时方法可能是更合理的方法，但既然您写道：“我知道如果我有一个可能匹配的列表...但是我想将两组单词分开 "，这可能不是您要找的。

我希望这会有所帮助。

于 2013-09-24T07:37:03.443 回答
0

存储您喜欢的单词并将可搜索的组合放入布隆过滤器中。

最一般形式的伪代码...：

插入：

for words in wordArray:
    bloomFilter.add( words.hash() )

搜索：

found = false
if bloomFilter.contains( searchedForWords.hash() ):
    if originalWordList.contains( words )
        found = true

关于布隆过滤器的一些注意事项：

  1. 查找内容非常快。
  2. 使用良好、快速的哈希函数。互联网上有很多
  3. 它可能会产生误报（X 在过滤器中，而实际上不在过滤器中）
  4. 它不能产生假阴性（X 不在过滤器中）
  5. 当布隆过滤器说过滤器中有东西时，您必须查看原始源数据以确保它确实存在。

我将此方法与一个应用程序防火墙一起使用，该防火墙旨在将色情和相关的垃圾从网络中隔离出来，与存储在传统的地图或哈希表中相比，它将特定代码的速度提高了 400 多倍。

于 2013-09-24T08:14:44.037 回答