查找字符串的公共前缀

Question

我有4个字符串：

"h:/a/b/c"
"h:/a/b/d"
"h:/a/b/e"
"h:/a/c"

我想找出这些字符串的公共前缀，例如"h:/a"。如何找到？

通常我会使用分隔符'/'将字符串拆分并放入另一个列表中等等。

有更好的方法吗？

- user251334

---

你的意思是要找出所有字符串中都相同的字符串，还是只有一个字符串在所有字符串中都相同？ - Andras Zoltan

h:/ 是一个驱动器吗？限制数据输入可以给出更适合您需求的答案。 - joetsuihk

我已经澄清了我理解的问题。如果有误，请回滚。 - dtb

Andras，我想要一个适用于所有的字符串。 - user251334

最长公共前缀为 h:/a/。 - user102008

Answer 1

string[] xs = new[] { "h:/a/b/c", "h:/a/b/d", "h:/a/b/e", "h:/a/c" };

string x = string.Join("/", xs.Select(s => s.Split('/').AsEnumerable())
                              .Transpose()
                              .TakeWhile(s => s.All(d => d == s.First()))
                              .Select(s => s.First()));

使用

public static IEnumerable<IEnumerable<T>> Transpose<T>(
    this IEnumerable<IEnumerable<T>> source)
{
    var enumerators = source.Select(e => e.GetEnumerator()).ToArray();
    try
    {
        while (enumerators.All(e => e.MoveNext()))
        {
            yield return enumerators.Select(e => e.Current).ToArray();
        }
    }
    finally
    {
        Array.ForEach(enumerators, e => e.Dispose());
    }
}

- dtb

---

一个聪明的函数式方法！感谢您的贡献，dtb——阅读您的看法总是很有趣。 - John Feminella

嘿，转置方法出现错误了... 告诉我要包含哪些命名空间... - user251334

.NET框架中没有“Transpose”方法。我使用了以下实现方式；不过，为了使其正常工作，必须将其中一个“First”调用更改为“FirstOrDefault”：http://www.extensionmethod.net/Details.aspx?ID=152 - dtb

好的，在 .Net 4 中不需要，但在 .Net 3.5 中需要：http://msdn.microsoft.com/zh-cn/library/system.string.join(VS.90).aspx http://msdn.microsoft.com/zh-cn/library/system.string.join.aspx - Simon D

请注意，如果传递空集合（所有返回值对于空集合都为真），Transpose实现将进入无限循环。此外，该实现包含潜在的内存泄漏 - 其中一个GetEnumerator方法可能会抛出异常，并且所有先前打开的枚举器将保持未处理状态。 - Alexander

Answer 2

我的一个简短的 LINQy 解决方案（使用 .NET 6 中的 MinBy）。

var samples = new[] { "h:/a/b/c", "h:/a/b/d", "h:/a/b/e", "h:/a/e" };
    
var commonPrefix = new string(samples.MinBy(s => s.Length)
        .TakeWhile((c, i) => samples.All(s => s[i] == c)).ToArray());

对于 .NET 5 及更早版本，请使用以下内容：

var samples = new[] { "h:/a/b/c", "h:/a/b/d", "h:/a/b/e", "h:/a/e" };
    
var commonPrefix = new string(
    samples.First().Substring(0, samples.Min(s => s.Length))
    .TakeWhile((c, i) => samples.All(s => s[i] == c)).ToArray());

- Yegor

---

不错的简短解决方案，比其他所有方案都更容易理解。 - MakePeaceGreatAgain

在这种情况下，.First().Substring(0, samples.Min(s => s.Length)) 可以被替换为 .Min()。 - Alex Telon

在我看来，这里的想法是获取列表中最短的字符串。.Min()并不一定会得到最短的字符串。{"aa", "b"}.Min()返回"aa"，因为"a"比"b"更低/更早地排序。 - Niko O

@NikoO 不过它不一定是最短的字符串。它可以是任何一个在s[i]处不会超出范围的字符串。Alex聪明的Min()建议满足了这个条件，使代码更加简洁。话虽如此，寻找最小的字符串比寻找最短的字符串要更昂贵。在.NET 6中，我会选择MinBy(s => s.Length)。 - Yegor

Answer 3

只需循环遍历最短字符串的字符，并将每个字符与其他字符串中相同位置的字符进行比较。只要它们都匹配，就继续向下执行。一旦出现不匹配的字符，则当前位置之前的字符串即为答案。

类似于以下的伪代码：

int count=0;
foreach(char c in shortestString)
{
    foreach(string s in otherStrings)
    {
        if (s[count]!=c)
        {
             return shortestString.SubString(0,count-1); //need to check count is not 0 
        }
    }
    count+=1;
 }
 return shortestString;

- Sam Holder

---

但是如果我有20个字符串..你认为逐个字符比较最短的字符串和其他字符串是有效的吗？ - user251334

如果你只有20个字符串，我认为你不需要担心效率问题，但是你需要检查每个字符串以确保它们是相同的，我不确定还能做些什么。如果你知道这些字符串可能在某种程度上是相同的，那么你可能可以做得更好。 - Sam Holder

如果您需要找到字符串中第一个不同的字符，则可以比较的最小字符数是每个字符串开头相同的字符数，再加上一个在一个字符串中与另一个字符串不同的字符。因此，这是可证明的最有效的查找共同前缀的算法。 - Greg Beech

没有问题。我对与dtb的答案进行分析比较感兴趣，这可能在多处理器机器上更有效。你也应该接受一个答案。 - Sam Holder

请注意，这里的命名标识了一个重要的依赖关系，即父级 foreach 循环实际上包含了 shortestString，否则在访问 sub[count] 时，每当 sub.Length == count 时，您将会得到一个 index out of bounds 异常 - 如果您无法保证这一点，请在您的方法中添加一个检查以提前返回... 在内部 foreach 循环中加入 if (sub.Length == count) return parent.Substring(0, count);。 - KyleMit

Answer 4

基于Sam Holder的解决方案编写的工作代码（请注意，它给出的是h:/a/而不是问题中最长的公共初始子串h:/a）：

using System;

namespace CommonPrefix
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(CommonPrefix(new[] { "h:/a/b/c", "h:/a/b/d", "h:/a/b/e", "h:/a/c" })); // "h:/a/"
            Console.WriteLine(CommonPrefix(new[] { "abc", "abc" })); // "abc"
            Console.WriteLine(CommonPrefix(new[] { "abc" })); // "abc"
            Console.WriteLine(CommonPrefix(new string[] { })); // ""
            Console.WriteLine(CommonPrefix(new[] { "a", "abc" })); // "a"
            Console.WriteLine(CommonPrefix(new[] { "abc", "a" })); // "a"

            Console.ReadKey();
        }

        private static string CommonPrefix(string[] ss)
        {
            if (ss.Length == 0)
            {
                return "";
            }

            if (ss.Length == 1)
            {
                return ss[0];
            }

            int prefixLength = 0;

            foreach (char c in ss[0])
            {
                foreach (string s in ss)
                {
                    if (s.Length <= prefixLength || s[prefixLength] != c)
                    {
                        return ss[0].Substring(0, prefixLength);
                    }
                }
                prefixLength++;
            }

            return ss[0]; // all strings identical up to length of ss[0]
        }
    }
}

- Simon D

---

一个小问题 - 你在代码底部的返回语句的注释中写着“所有字符串都相同”。这是不正确的。该函数执行的测试仅测试数组ss中其他字符串的根是否与ss[0]匹配，直到ss[0]的长度为止。数组ss中的其他字符串可能比ss[0]更长。尽管如此，我认为该代码已经正确执行了所需的任务。 - JHubbard80

Answer 5

这是最长公共子串问题（尽管这是一个略微特殊的情况，因为您似乎只关心前缀）。在.NET平台上没有算法的库实现可以直接调用，但此处链接的文章充满了自己如何完成它的步骤。

- John Feminella

---

我认为这个逻辑在这里行不通...我只想从第一个开始跟踪，当差异出现时停止。 - user251334

我给了这个+1，因为原问题并没有要求前缀，它只是要求公共子串（我们可能应该从数据中推断出它是否是前缀，但这不是被问到的）。 - Greg Beech

考虑到只搜索一个公共前缀，通用的最长公共子串算法将是一种可怕的过度杀伤（对于仅两个字符串而言，O(n^2)与O(n)相比...）。问题并不是“稍微专业化的情况”，而是更容易解决的问题 :-）。通常，我会给出-1（为了提供正确答案），但考虑到问题已经重新表述，我就不做修改了 :-) ... - MartinStettner

@MartinStettner 我不认为您应该投反对票来提升您认为正确的答案。您应该投反对票给您认为是错误的答案，并给您认为正确的答案投赞成票。如果足够多的人同意您的看法，答案将自然而然地上升到顶部。假设被标记为接受的答案是正确的，则正确答案将位于顶部。 - Sam Holder

我喜欢你将问题（无论是原始的还是其他的）带入了更广泛的视角。当然，我也喜欢对这个答案有自己的看法，显然，我不是唯一一个这样想的人。 :-) - jpaugh

Answer 6

这是一个使用C#自定义实现的trie算法(http://en.wikipedia.org/wiki/Trie)，用于通过前缀执行索引字符串。该类具有O(1)的叶节点写入和读取性能。对于前缀搜索，性能为O(log n)，但前缀结果的计数为O(1)。请注意保留HTML标签。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class StringIndex
{
    private Dictionary<char, Item> _rootChars;

    public StringIndex()
    {
        _rootChars = new Dictionary<char, Item>();
    }

    public void Add(string value, string data)
    {
        int level = 0;
        Dictionary<char, Item> currentChars = _rootChars;
        Item currentItem = null;

        foreach (char c in value)
        {
            if (currentChars.ContainsKey(c))
            {
                currentItem = currentChars[c];
            }
            else
            {
                currentItem = new Item() { Level = level, Letter = c };
                currentChars.Add(c, currentItem);                
            }

            currentChars = currentItem.Items;

            level++;
        }

        if (!currentItem.Values.Contains(data))
        {
            currentItem.Values.Add(data);
            IncrementCount(value);
        }
    }

    private void IncrementCount(string value)
    {
        Dictionary<char, Item> currentChars = _rootChars;
        Item currentItem = null;

        foreach (char c in value)
        {
            currentItem = currentChars[c];
            currentItem.Total++;
            currentChars = currentItem.Items;
        }
    }

    public void Remove(string value, string data)
    {
        Dictionary<char, Item> currentChars = _rootChars;
        Dictionary<char, Item> parentChars = null;
        Item currentItem = null;

        foreach (char c in value)
        {
            if (currentChars.ContainsKey(c))
            {
                currentItem = currentChars[c];
                parentChars = currentChars;
                currentChars = currentItem.Items;
            }
            else
            {
                return; // no matches found
            }
        }

        if (currentItem.Values.Contains(data))
        {
            currentItem.Values.Remove(data);
            DecrementCount(value);
            if (currentItem.Total == 0)
            {
                parentChars.Remove(currentItem.Letter);
            }
        }
    }

    private void DecrementCount(string value)
    {
        Dictionary<char, Item> currentChars = _rootChars;
        Item currentItem = null;

        foreach (char c in value)
        {
            currentItem = currentChars[c];
            currentItem.Total--;
            currentChars = currentItem.Items;
        }
    }

    public void Clear()
    {
        _rootChars.Clear();
    }

    public int GetValuesByPrefixCount(string prefix)
    {
        int valuescount = 0;

        int level = 0;
        Dictionary<char, Item> currentChars = _rootChars;
        Item currentItem = null;

        foreach (char c in prefix)
        {
            if (currentChars.ContainsKey(c))
            {
                currentItem = currentChars[c];
                currentChars = currentItem.Items;
            }
            else
            {
                return valuescount; // no matches found
            }
            level++;
        }

        valuescount = currentItem.Total;

        return valuescount;
    }

    public HashSet<string> GetValuesByPrefixFlattened(string prefix)
    {
        var results = GetValuesByPrefix(prefix);
        return new HashSet<string>(results.SelectMany(x => x));
    }

    public List<HashSet<string>> GetValuesByPrefix(string prefix)
    {
        var values = new List<HashSet<string>>();

        int level = 0;
        Dictionary<char, Item> currentChars = _rootChars;
        Item currentItem = null;

        foreach (char c in prefix)
        {
            if (currentChars.ContainsKey(c))
            {
                currentItem = currentChars[c];
                currentChars = currentItem.Items;
            }
            else
            {
                return values; // no matches found
            }
            level++;
        }

        ExtractValues(values, currentItem);

        return values;
    }

    public void ExtractValues(List<HashSet<string>> values, Item item)
    {
        foreach (Item subitem in item.Items.Values)
        {
            ExtractValues(values, subitem);
        }

        values.Add(item.Values);
    }

    public class Item
    {
        public int Level { get; set; }
        public char Letter { get; set; }
        public int Total { get; set; }
        public HashSet<string> Values { get; set; }
        public Dictionary<char, Item> Items { get; set; }

        public Item()
        {
            Values = new HashSet<string>();
            Items = new Dictionary<char, Item>();
        }
    }
}

这是该类的单元测试和使用示例代码。

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

    [TestClass]
    public class StringIndexTest
    {
        [TestMethod]
        public void AddAndSearchValues()
        {

            var si = new StringIndex();

            si.Add("abcdef", "1");
            si.Add("abcdeff", "2");
            si.Add("abcdeffg", "3");
            si.Add("bcdef", "4");
            si.Add("bcdefg", "5");
            si.Add("cdefg", "6");
            si.Add("cdefgh", "7");

            var output = si.GetValuesByPrefixFlattened("abc");

            Assert.IsTrue(output.Contains("1") && output.Contains("2") && output.Contains("3"));
        }

        [TestMethod]
        public void RemoveAndSearch()
        {

            var si = new StringIndex();

            si.Add("abcdef", "1");
            si.Add("abcdeff", "2");
            si.Add("abcdeffg", "3");
            si.Add("bcdef", "4");
            si.Add("bcdefg", "5");
            si.Add("cdefg", "6");
            si.Add("cdefgh", "7");

            si.Remove("abcdef", "1");

            var output = si.GetValuesByPrefixFlattened("abc");

            Assert.IsTrue(!output.Contains("1") && output.Contains("2") && output.Contains("3"));
        }

        [TestMethod]
        public void Clear()
        {

            var si = new StringIndex();

            si.Add("abcdef", "1");
            si.Add("abcdeff", "2");
            si.Add("abcdeffg", "3");
            si.Add("bcdef", "4");
            si.Add("bcdefg", "5");
            si.Add("cdefg", "6");
            si.Add("cdefgh", "7");

            si.Clear();
            var output = si.GetValuesByPrefix("abc");

            Assert.IsTrue(output.Count == 0);
        }

        [TestMethod]
        public void AddAndSearchValuesCount()
        {

            var si = new StringIndex();

            si.Add("abcdef", "1");
            si.Add("abcdeff", "2");
            si.Add("abcdeffg", "3");
            si.Add("bcdef", "4");
            si.Add("bcdefg", "5");
            si.Add("cdefg", "6");
            si.Add("cdefgh", "7");

            si.Remove("cdefgh", "7");

            var output1 = si.GetValuesByPrefixCount("abc");
            var output2 = si.GetValuesByPrefixCount("b");
            var output3 = si.GetValuesByPrefixCount("bc");
            var output4 = si.GetValuesByPrefixCount("ca");

            Assert.IsTrue(output1 == 3 && output2 == 2 && output3 == 2 && output4 == 0);
        }
    }

欢迎提出任何关于如何改进这个类的建议：）

- user896993

Answer 7

我需要一个通用的字符串前缀，但我希望包括任何字符（如 /），而且我不需要高性能/花哨的东西，只需要一些可以通过测试的可读内容。所以我有了这个：https://github.com/fschwiet/DreamNJasmine/commit/ad802611ceacc673f2d03c30f7c8199f552b586f。

public class CommonStringPrefix
{
    public static string Of(IEnumerable<string> strings)
    {
        var commonPrefix = strings.FirstOrDefault() ?? "";

        foreach(var s in strings)
        {
            var potentialMatchLength = Math.Min(s.Length, commonPrefix.Length);

            if (potentialMatchLength < commonPrefix.Length)
                commonPrefix = commonPrefix.Substring(0, potentialMatchLength);

            for(var i = 0; i < potentialMatchLength; i++)
            {
                if (s[i] != commonPrefix[i])
                {
                    commonPrefix = commonPrefix.Substring(0, i);
                    break;
                }
            }
        }

        return commonPrefix;
    }
}

- Frank Schwieterman

Answer 8

public string LongestCommonPrefix(string[] strs)
{
    return strs.Aggregate((seed,z) => string.Join("",seed.TakeWhile((v,i)=> z.Length > i && v == z[i])));
}

- Alex Veremeenko

Answer 9

我的方法是，先取第一个字符串。逐个字符比较，只要所有其他字符串在相同位置上都有相同的字符，就继续比较；如果没有匹配项，则停止比较。如果最后一个字符是分隔符，就将其删除。

var str_array = new string[]{"h:/a/b/c",
         "h:/a/b/d",
         "h:/a/b/e",
         "h:/a/c"};
var separator = '/';

// get longest common prefix (optinally use ToLowerInvariant)
var ret = str_array.Any() 
    ? str_array.First().TakeWhile((s,i) => 
         str_array.All(e => 
            Char.ToLowerInvariant(s) == Char.ToLowerInvariant(e.Skip(i).Take(1).SingleOrDefault()))) 
    : String.Empty;

// remove last character if it's a separator (optional)
if (ret.LastOrDefault() == separator) 
    ret = ret.Take(ret.Count() -1);

string prefix = new String(ret.ToArray());

- Bart Calixto

Answer 10

我编写了这个ICollection扩展来从Web地址集合中查找最长的共同基本URI。

由于它只在每个斜杠处检查字符串集合，因此它比通用前缀例程稍快（不计算我的低效算法！）。它很冗长，但易于理解...这是我最喜欢的代码类型 ;-)

忽略'http://'和'https://'，以及大小写。

    /// <summary>
    /// Resolves a common base Uri from a list of Uri strings. Ignores case. Includes the last slash
    /// </summary>
    /// <param name="collectionOfUriStrings"></param>
    /// <returns>Common root in lowercase</returns>
    public static string GetCommonUri(this ICollection<string> collectionOfUriStrings)
    {
        //Check that collection contains entries
        if (!collectionOfUriStrings.Any())
            return string.Empty;
        //Check that the first is no zero length
        var firstUri = collectionOfUriStrings.FirstOrDefault();
        if(string.IsNullOrEmpty(firstUri))
            return string.Empty;

        //set starting position to be passed '://'
        int previousSlashPos = firstUri.IndexOf("://", StringComparison.OrdinalIgnoreCase) + 2;
        int minPos = previousSlashPos + 1; //results return must have a slash after this initial position
        int nextSlashPos = firstUri.IndexOf("/", previousSlashPos + 1, StringComparison.OrdinalIgnoreCase);
        //check if any slashes
        if (nextSlashPos == -1)
            return string.Empty;

        do
        {               
            string common = firstUri.Substring(0, nextSlashPos + 1);
            //check against whole collection
            foreach (var collectionOfUriString in collectionOfUriStrings)
            {
                if (!collectionOfUriString.StartsWith(common, StringComparison.OrdinalIgnoreCase))
                {
                    //return as soon as a mismatch is found
                    return previousSlashPos > minPos ? firstUri.Substring(0, previousSlashPos + 1).ToLower() : string.Empty ;
                }
            }
            previousSlashPos = nextSlashPos;                
            nextSlashPos = firstUri.IndexOf("/", previousSlashPos + 1, StringComparison.OrdinalIgnoreCase);
        } while (nextSlashPos != -1);

        return previousSlashPos > minPos ? firstUri.Substring(0, previousSlashPos + 1).ToLower() : string.Empty;
    } 

- NER1808