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

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/

我想避免 char by char 比较。

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);