Найти общий префикс строк

Улучшение на ответе Yegor

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

var commonPrefix = new string(
    samples.Min().TakeWhile((c, i) => samples.All(s => s[i] == c)).ToArray());

Первый мы знаем, что самый длинный общий префикс не может быть длиннее, чем самый короткий элемент. Поэтому возьмите самый короткий и возьмите символы от него, в то время как все другие строки имеют тот же символ в том же положении. В крайнем случае мы берем все символы от самого короткого элемента. Путем итерации по самому короткому элементу индексный поиск не выдаст исключений.

Другой (хуже, но все еще интересный) способ решить его с помощью LINQ был бы этим:

samples.Aggregate(samples.Min(), (current, next) => new string(current.TakeWhile((c,i) => next[i] == c).ToArray() ));

Эти работы путем создания commonPrefix и сравнения этого с каждым элементом один за другим. В каждом сравнении commonPrefix или сохраняется или уменьшается. В первом текущем повторении минимальный элемент, но каждое повторение после этого это - лучший commonPrefix, найденный до сих пор. Думайте об этом как о глубине первое решение, в то время как первый является в ширину.

Этот тип решения мог бы быть улучшен путем сортировки образцов с точки зрения длины так, чтобы самые короткие элементы были сравнены сначала.

Этот тип решения не может действительно быть лучше, чем первое как бы то ни было. В лучшем случае это как - хорошо как первое решение. Но иначе это сделает дополнительную работу путем нахождения временных commonPrefixes, которые длиннее, чем необходимый.

Это - простой метод, который находит общий строковый префикс.

public static string GetCommonStartingPath(string[] keys)
        {
            Array.Sort(keys, StringComparer.InvariantCulture);
            string a1 = keys[0], a2 = keys[keys.Length - 1];
            int L = a1.Length, i = 0;
            while (i < L && a1[i] == a2[i])
            {
                i++;
            }

            string result = a1.Substring(0, i);

            return result;
        }

Это является проблемой , длинная простая подстрока проблема (хотя это немного специализированный случай, поскольку вы, кажется, заботитесь о префиксе). В платформе .NET нет реализации алгоритма библиотеки.

Просто петля вокруг символов кратчайшей строки и сравните каждого персонажа к символу в той же положении в других строках. Пока они все матч продолжают идти. Как только не совпадает, то строка до текущей позиции -1 является ответом.

Что-то вроде (псевдо-код)

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;

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

Рабочий код, основанный на решении Сэма Холдера (обратите внимание, что в качестве самой длинной общей начальной подстроки в вопросе указано h: / a / not 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]
        }
    }
}