如何在 c++ 中找到第一个唯一字符 list<string>？

定义数据集的最佳和大小。 它是一棵树，因此您可以将路径插入树中，然后遍历，直到找到具有多个子节点的节点，此节点是所有节点的公共路径。

这是一种一阶方法，（太糟糕了，我在<filesystem>)

#include <string>
#include <vector>
#include <iostream>

std::string get_common_path(const std::string& lhs, const std::string& rhs)
{
    auto lhs_it = lhs.begin();
    auto rhs_it = rhs.begin();

    // as long as characters match move to right (but not past end of either string)
    while ((lhs_it != lhs.end()) && (rhs_it != rhs.end()) && (*lhs_it == *rhs_it))
    {
        ++lhs_it;
        ++rhs_it;
    }

    return std::string{ lhs.begin(),lhs_it };
}

std::string common_path(const std::vector<std::string>& values)
{
    if (values.empty()) return std::string{};
    if (values.size() == 1) return values.front();

    // get first string, that is now most common path
    auto it = values.begin();
    std::string retval = *it;
    ++it;
    
    // loop over all values
    while ((it != values.end()) && (!retval.empty()))
    {
        // the overlap is the existing overlap combined with the next string
        // in the vector.
        retval = get_common_path(retval, *it);
        ++it;
    }
    
    return retval;
}


int main()
{
    std::vector<std::string> paths
    {
        "/a/ab/bc/de",
        "/a/ab/cc/fw",
        "/a/ab/dd",
        "/a/ab/ee/fg"
    };

    auto result = common_path(paths);
    std::cout << result;
    
    return 0;
}

首先对路径向量进行排序。

std::vector<std::string> paths = {"/a/ab/bc/de", "/a/b/cc/fw", "/a/ab/dd", "/a/ab/ee/fg"};
std::sort(paths.begin(), paths.end());

比较最短路径和最长路径以查找位置不匹配。

const auto& shortest = paths.front();
const auto& longest = paths.back();
auto mis = std::mismatch(shortest.cbegin(), shortest.cend(), longest.cbegin(), longest.cend());

现在从子字符串复制。

auto common = std::string(shortest.cbegin(), mis.first);

以下是在 vs2022 中测试的完整源代码。 它打印了“/a/ab/”和“/a/”作为您的示例。 我相信您可以找到如何删除尾随的“/”。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
  try {
    std::vector<std::string> paths = {"/a/ab/bc/de", "/a/b/cc/fw", "/a/ab/dd",
                                      "/a/ab/ee/fg"};

    std::sort(paths.begin(), paths.end());

    const auto& shortest = paths.front();
    const auto& longest = paths.back();
    auto mis = std::mismatch(shortest.cbegin(), shortest.cend(),
                             longest.cbegin(), longest.cend());

    auto common = std::string(shortest.cbegin(), mis.first);
    std::cout << common << std::endl;
  } catch (const std::exception& e) {
    std::cerr << e.what() << std::endl;
    return -1;
  }

  return 0;
}

有一个非常简单的解决方案。

您可以分析数据并进行以下观察。

如果将 视为 2 维字符数组，则可以比较字符列。std::vector<std::string>>

/a/ab/bc/de
/a/b/cc/fw      
/a/ab/dd
/a/ab/ee/fg
||||
||||
|||+--- Not all charatcers are the same 
||+---- All characters in this column are the same
|+----- All characters in this column are the same
+------ All characters in this column are the same

从第 0 列开始，您可以检查此列中的所有字符是否相同，然后是下一列，依此类推。

一旦我们发现一列中的差异，那么我们就知道我们已经找到了通用前缀的末尾。

然后我们可以输出通用前缀的结果以及剩余的后缀。

所有这一切都只需要几行常规代码。

一个潜在解决方案的示例：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::vector<std::string> paths = { "/a/ab/bc/de", "/a/b/cc/fw", "/a/ab/dd", "/a/ab/ee/fg" };

int main() {
    // Sanity check
    if (not paths.empty()) {

        // Of course we will only compare to the smallest string size
        size_t minSize = std::min_element(paths.begin(), paths.end(), [](const std::string& s1, const std::string& s2) {return s1.size() < s2.size(); })->size();
        size_t cont{ 1 }, col{ 0 };

        // Double nested loop to find resutling column
        for (size_t row{ 1 }; cont and col < minSize; col += cont, row = 1)
            for (auto c{ paths.front()[col] }; cont and row < paths.size(); row += cont)
                cont = ((c == paths[row][col]) * 1);

        // Show result as debug output
        std::cout << "Common prefix: " << paths.front().substr(0, col) << "\n\n";
        for (std::string& s : paths) std::cout << "Resulting path: " << s.substr(col) << '\n';
    }
}