c++ - 如何切断字符串的一部分，集合中的每个字符串都有

Question

我目前的问题如下: 我有一个文件的完整路径名的std::vector。 现在我想切断所有字符串的公共(public)前缀。

例子

如果我在 vector 中有这 3 个字符串:

/home/user/foo.txt
/home/user/bar.txt
/home/baz.txt

我想从 vector 中的每个字符串中删除 /home/。

问题

一般有什么方法可以做到这一点吗？ 我想要一个算法来删除所有字符串的公共(public)前缀。 我目前只有一个想法可以在 O(n m) 中用 n 字符串解决这个问题，m 是最长的字符串长度，只需逐个字符地遍历每个字符串和其他所有字符串。 有没有更快或更优雅的方法来解决这个问题？

Answer 1

这完全可以用 std::算法来完成。

内容简介:

1. 如果尚未排序，则对输入范围进行排序。排序范围内的第一个和最后一个路径 将是最不同的。最好的情况是 O(N)，最坏的情况是 O(N + N.logN)

2. 使用 std::mismatch 来确定 两条最不同的路径[无关紧要]

3. 遍历每条路径，删除前 COUNT 个字符，其中 COUNT 是最长公共(public)序列中的字符数。 O(N)

最佳情况时间复杂度:O(2N)，最坏情况 O(2N + N.logN)(有人可以检查一下吗？)

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

std::string common_substring(const std::string& l, const std::string& r)
{
    return std::string(l.begin(),
                       std::mismatch(l.begin(), l.end(),
                                     r.begin(), r.end()).first);
}

std::string mutating_common_substring(std::vector<std::string>& range)
{
    if (range.empty())
        return std::string();
    else
    {
        if (not std::is_sorted(range.begin(), range.end()))
            std::sort(range.begin(), range.end());
        return common_substring(range.front(), range.back());
    }
}

std::vector<std::string> chop(std::vector<std::string> samples)
{
    auto str = mutating_common_substring(samples);
    for (auto& s : samples)
    {
        s.erase(s.begin(), std::next(s.begin(), str.size()));
    }
    return samples;
}

int main()
{
    std::vector<std::string> samples = {
        "/home/user/foo.txt",
        "/home/user/bar.txt",
        "/home/baz.txt"
    };

    samples = chop(std::move(samples));

    for (auto& s : samples)
    {
        std::cout << s << std::endl;
    }   
}

预期:

baz.txt
user/bar.txt
user/foo.txt

这是一个不需要排序的备用“common_substring”。时间复杂度在理论上是 O(N) 但在实践中它是否更快你必须检查:

std::string common_substring(const std::vector<std::string>& range)
{
    if (range.empty())
    {
        return {};
    }

    return std::accumulate(std::next(range.begin(), 1), range.end(), range.front(),
                           [](auto const& best, const auto& sample)
                           {
                               return common_substring(best, sample);
                           });
}

更新:

撇开优雅不谈，这可能是最快 的方式，因为它避免了任何内存分配，就地执行所有转换。对于大多数架构和样本大小，这比任何其他性能考虑因素都更重要。

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

void reduce_to_common(std::string& best, const std::string& sample)
{
    best.erase(std::mismatch(best.begin(), best.end(),
                             sample.begin(), sample.end()).first,
               best.end());

}

void remove_common_prefix(std::vector<std::string>& range)
{
    if (range.size())
    {
        auto iter = range.begin();
        auto best = *iter;
        for ( ; ++iter != range.end() ; )
        {
            reduce_to_common(best, *iter);
        }

        auto prefix_length = best.size();

        for (auto& s : range)
        {
            s.erase(s.begin(), std::next(s.begin(), prefix_length));
        }
    }
}


int main()
{
    std::vector<std::string> samples = {
        "/home/user/foo.txt",
        "/home/user/bar.txt",
        "/home/baz.txt"
    };

    remove_common_prefix(samples);

    for (auto& s : samples)
    {
        std::cout << s << std::endl;
    }   
}