查找多个字符串的公共前缀的最有效方法

Question

查找多个字符串的公共前缀的最有效方法是什么。

例如：

对于这组字符串

/home/texai/www/app/application/cron/logCron.log
/home/texai/www/app/application/jobs/logCron.log
/home/texai/www/app/var/log/application.log
/home/texai/www/app/public/imagick.log
/home/texai/www/app/public/status.log

我想要

/home/texai/www/app/

我想避免逐个字符的比较。

Answer 1

您无法避免至少通过公共部分来查找公共前缀。

我认为这不需要任何花哨的算法。只需跟踪当前的公共前缀，然后通过将当前前缀与下一个字符串进行比较来缩短前缀。

由于这是所有字符串的公共前缀，因此您最终可能会得到空字符串（没有公共前缀）。

Answer 2

我不确定避免逐个字符比较是什么意思，但您至少需要从每个字符串中读取公共前缀，因此以下算法是您可以实现的最佳算法（只需迭代字符串，直到它们偏离或直到达到当前最长前缀计数）：

List<string> list = new List<string>()
{
    "/home/texai/www/app/application/cron/logCron.log",
    "/home/texai/www/app/application/jobs/logCron.log",
    "/home/texai/www/app/var/log/application.log",
    "/home/texai/www/app/public/imagick.log",
    "/home/texai/www/app/public/status.log"
};

int maxPrefix = list[0].Length;
for(int i = 1; i < list.Count; i++)
{
    int pos = 0;
    for(; pos < maxPrefix && pos < list[i].Length && list[0][pos] == list[i][pos]; pos++);

    maxPrefix = pos;
}

//this is the common prefix
string prefix = list[0].Substring(0, maxPrefix);

Answer 3

字符尝试。一种树状数据结构，用于存储动态字符串集，其中每个节点代表单个字符。

#include <unordered_map>
#include <string_view>
#include <memory>
#include <iostream>


// A trie of characters.
class CharTrie final
{
public:

    // Function to insert a string into the trie.
    void Insert(const std::string_view string_view)
    {
        if (!string_view.empty()) {
            Insert(root_node_, string_view);
            ++size_;
        }
    }


    // Function to find the common prefix among trie strings.
    auto CommonPrefix() const
    {
        std::string common_prefix{};

        CommonPrefix(root_node_, common_prefix);

        return common_prefix;
    }

private:

    // Structure representing a node in the trie.
    struct Node final
    {
        uint32_t count{ 0 }; // Counts how many times a character appears at this level.
        std::unordered_map<char, std::unique_ptr<Node>> child_node{}; // Map of child nodes.
    };

    Node root_node_{}; // Root node of the trie (Represents a null prefix.)
    size_t size_{ 0 }; // Total number of inserted strings.


    // Recursive function to insert a string into the trie.
    void Insert(Node& root, const std::string_view string_view)
    {
        if (string_view.empty()) {
            return;
        }

        char first_char = string_view[0]; // Get the first character of the string.
        std::string_view remaining_view = string_view.substr(1); // Get the substring starting from index 1.

        if (root.child_node.find(first_char) == root.child_node.end()) {
            // If the character does not exist in the trie, create a new node and insert it into the child nodes map.
            root.child_node[first_char] = std::make_unique<Node>();
        }

        root.child_node[first_char]->count++; // Increment the the character count at this level.
        Insert(*root.child_node[first_char], remaining_view); // Recursively insert the remaining substring.
    }


    // Recursive function to find the common prefix among all inserted strings.
    void CommonPrefix(const Node& root, std::string& common_prefix) const
    {
        // For a common prefix character, only one child node is expected.
        if (root.child_node.size() != 1) {
            return;
        }

        // Even with only one child node, the count must be at the size_ value.
        if (root.child_node.begin()->second->count != size_) {
            return;
        }

        common_prefix += root.child_node.begin()->first; // Append the current character to the common prefix.
        CommonPrefix(*root.child_node.begin()->second, common_prefix); // Recursively find the common prefix in the next node.
    }
};


int main()
{
    // Create a trie object.
    CharTrie trie{};

    // Insert strings into the trie.
    trie.Insert("/home/texai/www/app/application/cron/logCron.log");
    trie.Insert("/home/texai/www/app/application/jobs/logCron.log");
    trie.Insert("/home/texai/www/app/var/log/application.log");
    trie.Insert("/home/texai/www/app/public/imagick.log");
    trie.Insert("/home/texai/www/app/public/status.log");

    // Find and print the common prefix among all inserted strings.
    std::cout << "common prefix: " << trie.CommonPrefix() << std::endl;
}

输出：

common prefix: /home/texai/www/app/

演示