在文件和目录列表中查找公共父路径

Question

我有一个文件和目录列表List<string> pathes.现在我想计算每个路径彼此共享的最深的公共分支.

我们可以假设它们都有共同的路径,但这在开始时是未知的.

假设我有以下三个条目:

• C:/Hello/World/This/Is/An/Example/Bla.cs
• C:/你好/世界/这/是/不是/ AN /示例/
• C:/您好/地球/ BLA/BLA/BLA

这应该得到结果:C:/ Hello /因为地球正在打破子目录的这个"链".

第二个例子:

• C:/Hello/World/This/Is/An/Example/Bla.cs
• C:/你好/世界/这/是/不是/ AN /示例/

- > C:/ Hello/World/This/Is /

你会怎么做？我尝试使用string.split(@"/")并从第一个字符串开始,并检查此数组的每个部分是否包含在其他字符串中.但是,这将是一个非常昂贵的调用,因为我正在迭代(list_of_entries)^ list_of_entries.有没有更好的解决方案？

我目前的尝试将类似于以下(C#+ LINQ):

    public string CalculateCommonPath(IEnumerable<string> paths)
    {
        int minSlash = int.MaxValue;
        string minPath = null;
        foreach (var path in paths)
        {
            int splits = path.Split('\\').Count();
            if (minSlash > splits)
            {
                minSlash = splits;
                minPath = path;
            }
        }

        if (minPath != null)
        {
            string[] splits = minPath.Split('\\');
            for (int i = 0; i < minSlash; i++)
            {
                if (paths.Any(x => !x.StartsWith(splits[i])))
                {
                    return i >= 0 ? splits.Take(i).ToString() : "";
                }
            }
        }
        return minPath;
    }

Answer 1

我不知道这是否是性能最佳的解决方案(可能不是),但它确实很容易实现.

• 按字母顺序排序列表
• 比较该排序列表中的第一个条目与该列表中的最后一个条目,逐个字符,并在找到差异时终止(终止前的值是这两个字符串中最长的共享子字符串)

样品小提琴

示例代码:

List<string> paths = new List<string>();

paths.Add(@"C:/Hello/World/This/Is/An/Example/Bla.cs");
paths.Add(@"C:/Hello/World/This/Is/Not/An/Example/");
paths.Add(@"C:/Hello/Earth/Bla/Bla/Bla");

List<string> sortedPaths = paths.OrderBy(s => s).ToList();

Console.WriteLine("Most common path here: {0}", sharedSubstring(sortedPaths[0], sortedPaths[sortedPaths.Count - 1]));

那个功能当然是:

public static string sharedSubstring(string string1, string string2)
{
    string ret = string.Empty;

    int index = 1;
    while (string1.Substring(0, index) == string2.Substring(0, index))
    {
        ret = string1.Substring(0, index);
        index++;
    }

    return ret;
} // returns an empty string if no common characters where found

Answer 2

获取最长公共前缀的函数可能如下所示:

public static string GetLongestCommonPrefix(string[] s)
{
    int k = s[0].Length;
    for (int i = 1; i < s.Length; i++)
    {
        k = Math.Min(k, s[i].Length);
        for (int j = 0; j < k; j++)
            if (s[i][j] != s[0][j])
            {
                k = j;
                break;
            }
    }
    return s[0].Substring(0, k);
}

然后你可能需要在右边剪切前缀.例如,我们要返回c:/dir,而不是 c:/dir/file为

c:/dir/file1
c:/dir/file2

您还可能希望在处理之前规范化路径.请参阅在C#中规范化目录名称.