我们有像 name:location 这样的字符串对的映射(unix 就像绝对位置 a lamyfolder/
)。我们得到了一些位置a lamyfolder/mysubfolder/myfile
。如何找到哪个地图位置最适合给定的网址?
例如我们有一个这样的地图:
service1:myfolder/
service2:myfolder/mysubfolder/
service3:myfolder/myothersubfolder/
service4:myfolder/mysubfolder/myfile
我们被赋予价值myfolder/mysubfolder/myfile/blablabla/
(细绳)。
我们想要找出它与地图中的哪个项目最相关。
搜索结果应为service4
作为具有最相关内容的地图项。
那么如何根据给定的字符串值找到与哪个映射元素最相关的呢?
请提供一些代码,因为我是 C++ nube,不知道如何实现这样的事情?
所以我稍微简化了一个问题 -现在我需要的所有关系是给定路径的深度 https://stackoverflow.com/questions/5997723/having-a-map-with-paths-how-to-compare-tham-to-given-path在字符串情况下,只需迭代所有地图路径,查看长度,搜索给定路径中的出现并记住给定路径中找到的最长地图项路径即可实现。
有两种选择:
- If you need to run many queries:
- 构建逆映射或使用双向映射。
- Find first larger element using upper_bound and
- 如果您需要具有最长公共前缀的元素,请检查此元素和前一个(最后一个较小的)元素,并选择具有较长公共前缀的元素。
- 如果您需要作为前缀的元素,请向后扫描,直到找到作为前缀的元素。
- 如果您只需要一个查询,简单的线性搜索会更快(构建逆映射需要O(n log(n)),而一次迭代只需要O(n)),而且更容易实现。只需迭代地图,为每个值计算前缀长度并记住迄今为止的最佳匹配(我想建议使用
std::max_element
,但它通过比较运算符实现最大值,而您需要通过指标获得最大值)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)