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

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

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/file1
c:/dir/file2

您还可能希望在处理之前对路径进行规范化。

我不知道这是否是最好的解决方案(可能不是)，但它肯定是非常容易实现的。

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

示例代码:

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

首先用要检查的路径对列表进行排序。然后，您可以拆分并比较第一项和最后一项—如果它们相同，则继续到下一个维度，直到找到差异。

所以你只需要排序一次，然后检查两个项目。

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

我将这样编码:

public static string GetLongestCommonPrefix(params string[] s)
{
    return GetLongestCommonPrefix((ICollection<string>)s);
}
public static string GetLongestCommonPrefix(ICollection<string> paths)
{
    if (paths == null || paths.Count == 0)
        return null;

    if (paths.Count == 1)
        return paths.First();
    var allSplittedPaths = paths.Select(p => p.Split('''')).ToList();
    var min = allSplittedPaths.Min(a => a.Length);
    var i = 0;
    for (i = 0; i < min; i++)
    {
        var reference = allSplittedPaths[0][i];
        if (allSplittedPaths.Any(a => !string.Equals(a[i], reference, StringComparison.OrdinalIgnoreCase)))
        {
            break;
        }
    }
    return string.Join("''", allSplittedPaths[0].Take(i));
}

这里有一些测试:

[TestMethod]
public void GetLongestCommonPrefixTest()
{
    var str1 = @"C:'dir'dir1'file1";
    var str2 = @"C:'dir'dir1'file2";
    var str3 = @"C:'dir'dir1'file3";
    var str4 = @"C:'dir'dir2'file3";
    var str5 = @"C:'dir'dir1'file1'file3";
    var str6 = @"C:'dir'dir1'file1'file3";

    var res = Utilities.GetLongestCommonPrefix(str1, str2, str3);
    Assert.AreEqual(@"C:'dir'dir1", res);
    var res2 = Utilities.GetLongestCommonPrefix(str1, str2, str3, str4);
    Assert.AreEqual(@"C:'dir", res2);
    var res3 = Utilities.GetLongestCommonPrefix(str1, str2, str3, str5);
    Assert.AreEqual(@"C:'dir'dir1", res3);
    var res4 = Utilities.GetLongestCommonPrefix(str5, str6);
    Assert.AreEqual(@"C:'dir'dir1'file1'file3", res4);
    var res5 = Utilities.GetLongestCommonPrefix(str5);
    Assert.AreEqual(str5, res5);
    var res6 = Utilities.GetLongestCommonPrefix();
    Assert.AreEqual(null, res6);
    var res7 = Utilities.GetLongestCommonPrefix(null);
    Assert.AreEqual(null, res7);
}

我会遍历第一个路径中的每个字符，将其与路径集合中每个路径(除了第一个路径)中的每个字符进行比较:

public string FindCommonPath(List<string> paths)
{
    string firstPath = paths[0];
    bool same = true;
    int i = 0;
    string commonPath = string.Empty;
    while (same && i < firstPath.Length)
    {
        for (int p = 1; p < paths.Count && same; p++)
        {
            same = firstPath[i] == paths[p][i];
        }
        if (same)
        {
            commonPath += firstPath[i];
        }
        i++;
    }
    return commonPath;
}

您可以首先遍历列表以找到最短路径，并可能稍微改进它。

为您提供具有最佳复杂性的最长公共目录路径的函数:

private static string GetCommonPath(IEnumerable<string> files)
{
    // O(N, L) = N*L; N  - number of strings, L - string length
    // if the first and last path from alphabetic order matches, all paths in between match
    string first = null;//smallest string
    string last = null;//largest string
    var comparer = StringComparer.InvariantCultureIgnoreCase;
    // find smallest and largest string:
    foreach (var file in files.Where(p => !string.IsNullOrWhiteSpace(p)))
    {
        if (last == null || comparer.Compare(file, last) > 0)
        {
            last = file;
        }
        if (first == null || comparer.Compare(file, first) < 0)
        {
            first = file;
        }
    }
    if (first == null)
    {
        // the list is empty
        return string.Empty;
    }
    if (first.Length > last.Length)
    {
        // first should not be longer
        var tmp = first;
        first = last;
        last = tmp;
    }
    // get minimal length
    var count = first.Length;
    var found = string.Empty;
    const char dirChar = '''';
    var sb = new StringBuilder(count);
    for (var idx = 0; idx < count; idx++)
    {
        var current = first[idx];
        var x = char.ToLowerInvariant(current);
        var y = char.ToLowerInvariant(last[idx]);
        if (x != y)
        {
            // first and last string character is different - break
            return found;
        }
        sb.Append(current);
        if (current == dirChar)
        {
            // end of dir character
            found = sb.ToString();
        }
    }
    if (last.Length >= count && last[count] == dirChar)
    {
        // whole first is common root:
        return first;
    }
    return found;
}

这比用斜杠分割路径并比较它们要优化得多:

private static string FindCommonPath(string[] paths) {
    var firstPath = paths[0];
    var commonPathLength = firstPath.Length;
    for (int i = 1; i < paths.Length; i++)
    {
        var otherPath = paths[i];
        var pos = -1;
        var checkpoint = -1;
        while (true)
        {
            pos++;
            if (pos == commonPathLength)
            {
                if (pos == otherPath.Length
                    || (pos < otherPath.Length
                        && (otherPath[pos] == '/' || otherPath[pos] == '''')))
                {
                    checkpoint = pos;
                }
                break;
            }
            if (pos == otherPath.Length)
            {
                if (pos == commonPathLength
                || (pos < commonPathLength
                    && (firstPath[pos] == '/' || firstPath[pos] == '''')))
                {
                    checkpoint = pos;
                }
                break;
            }
            if ((firstPath[pos] == '/' || firstPath[pos] == '''')
                && (otherPath[pos] == '/' || otherPath[pos] == ''''))
            {
                checkpoint = pos;
                continue;
            }
            var a = char.ToLowerInvariant(firstPath[pos]);
            var b = char.ToLowerInvariant(otherPath[pos]);
            if (a != b)
                break;
        }
        if (checkpoint == 0 && (firstPath[0] == '/' || firstPath[0] == ''''))
            commonPathLength = 1;
        else commonPathLength = checkpoint;
        if (commonPathLength == -1 || commonPathLength == 0)
            return "";
    }
    return firstPath.Substring(0, commonPathLength);
}