c++ - 仅匹配集合中的某些字段

Question

背景

我正在尝试使用散列查找公共子字符串，为此我首先遍历我的第一个字符串并创建一个set<pair<int,int>>包含来自两个不同散列函数的散列值的可能长度为“ l ”的子字符串。然后我遍历第二个字符串和长度为“ l ”的子字符串。我计算哈希对并检查它们是否存在于集合中。

问题

我需要找到子字符串的开头，同时还要利用 stl::set 提供的更快的查找时间。我不能使用distance(set.begin(),set.myValue'sPos)，因为该集合会自动排序。

解决方案尝试

1. 我想创建一个结构，{ Hash val1, Hash val2, startPos}但是我将无法使用 find 函数，因为来自 string1 和 string2 的子字符串的 startPos 会不同。

2. 我知道我可以修改我的结构的 == 运算符以使用 find 函数，但我担心它会影响它的运行时间？

（TL;DR - 简单来说，修改 == 操作会影响 stl find 函数的运行时间）

有没有更好的方法来做到这一点？

问题示例

假设我的字符串是'abcd' and 'dcfcd'，我正在寻找的长度是 2。

在集合中 -hash('ab'), hash('bc') and hash('cd')被插入。（其中每一个都是一对 int，从两个 diff hash fns 获得的数字）。

然后我遍历第二个字符串并检查hash('dc'), hash('cf'),hash('fc') and hash('cd')集合中是否存在。 hash('cd')确实存在于集合中，现在我想知道两个字符串中“cd”的位置。

对于 'dcfcd' 这很简单，因为我可以从循环中获取值。但我还需要在“abcd”中找到“cd”的位置。如果容器没有排序，那么我会知道“cd”是容器的第三个元素，因此位于位置 3。

标签： c++hashstlset

Answer 1

你可以使用 set.find()。据我所知，在为某些对象搜索集合时，您会受到性能影响。使用 std::set 很可能无法解决它。