有一个字符串映射如何将其与给定字符串进行比较

Question

我们有像名字一样的字符串对的映射：位置（像绝对位置一样的unix a la myfolder/）。我们给了一些地点la myfolder/mysubfolder/myfile。如何找到最适合给定网址的地图位置？

例子，我们有一个地图，如：

service1:myfolder/ 
service2:myfolder/mysubfolder/ 
service3:myfolder/myothersubfolder/ 
service4:myfolder/mysubfolder/myfile 

我们给定值myfolder/mysubfolder/myfile/blablabla/（串）。 我们想知道它与我们地图中哪个项目最相关。 搜索结果为service4为最相关内容的地图项。

那么如何通过给定的字符串值来查找它最相关的地图元素呢？

请提供一些代码，因为我是C++ nube，不知道如何实现这样的事情？

所以我简化了一个问题 - now all relation I need is in how deep given path is在字符串的情况下，可以通过遍历所有地图路径来查看长度，寻找给定路径的出现并记住在给定路径中找到的最长地图项目路径。

Answer 1

如果地图的定义是这样的：

typedef std::map<std::string,std::string> MyMap; 
MyMap my_map; 

...和搜索词的定义是这样的：

std::string my_key_to_find = "service4"; 

...那么你就可以得到与此相关的值关键是这样的：

std::string found_val; 
MyMap::const_iterator it = my_map.find(my_key_to_find); 
if(it != my_map.end()) 
    found_val = it->second; 
else 
    std::cout << "Key not found!\n"; 

Answer 2

有两种选择：

1. 如果您需要运行很多查询：
   1. 构建反向映射或使用双向映射。
   2. 使用UPPER_BOUND查找第一大要素和
      • 如果您需要最长的公共前缀元素，看看这个和以前（最后小）元素，并选择一个较长的公共前缀。
      • 如果您需要作为前缀的元素，请回溯扫描，直至找到作为前缀的元素。
2. 如果你只需要一个查询，简单的线性搜索会更快（构建逆映射需要O（N日志（N）），而一个迭代只需为O（n） ），再加上它更容易实现。只需遍历地图，为每个值计算前缀长度，并记住目前为止的最佳匹配（我想建议使用std::max_element，但它通过比较运算符实现最大值，而通过度量需要最大值）。

Answer 3

如果我正确理解您的问题，您希望通过值（字符串）搜索键，其中匹配值是提供的搜索词的子字符串。我认为这不是一个简单的解决方案，因为这是一个普遍问题（即任意字符串及其所有子字符串）。

但是，在您的示例中用作值的字符串具有特定的结构（即文件系统路径）。你可以利用这个结构来提出一个干净的解决方案。首先，制作bi-directional map。然后，执行以下查找过程：

1. 如果路径为空，则失败。
2. 根据请求路径在地图上进行反向查找
3. 如果找到，返回相关值。
4. 从路径中弹出最后一个组件。
5. Loop。

如果列表很短，您可能只想遍历（键，值）对列表并选择值最相似的键（即最长的子字符串）。