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

Question

У меня 4 строки:

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

Я хочу найти общий префикс для этих строк, т.е. "h:/a". Как это найти?

Обычно я разделяю строку с разделителем '/' и помещаю ее в другой список и т. Д.
Есть ли лучший способ сделать это?

Answer 1

Здесь я реализовал довольно эффективный метод, когда вы должны анализировать огромное количество строк, здесь я также кеширую количество и длину, что повышает производительность примерно в 1,5 раза в моих тестах по сравнению с доступом к свойствам в циклах:

using System.Collections.Generic;
using System.Text;

........

public static string GetCommonPrefix ( IList<string> strings )
{
    var stringsCount = strings.Count;
    if( stringsCount == 0 )
        return null;
    if( stringsCount == 1 )
        return strings[0];

    var sb = new StringBuilder( strings[0] );
    string str;
    int i, j, sbLen, strLen;

    for( i = 1; i < stringsCount; i++ )
    {
        str = strings[i];

        sbLen = sb.Length;
        strLen = str.Length;
        if( sbLen > strLen )
            sb.Length = sbLen = strLen;

        for( j = 0; j < sbLen; j++ )
        {
            if( sb[j] != str[j] )
            {
                sb.Length = j;
                break;
            }
        }
    }

    return sb.ToString();
}

UPD: Я также реализовал параллельную версию, которая использует вышеуказанный метод в качестве последнего шага:

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

........

public static string GetCommonPrefixParallel ( IList<string> strings )
{
    var stringsCount = strings.Count;
    if( stringsCount == 0 )
        return null;
    if( stringsCount == 1 )
        return strings[0];

    var firstStr = strings[0];
    var finalList = new List<string>();
    var finalListLock = new object();

    Parallel.For( 1, stringsCount,
        () => new StringBuilder( firstStr ),
        ( i, loop, localSb ) =>
        {
            var sbLen = localSb.Length;
            var str = strings[i];
            var strLen = str.Length;
            if( sbLen > strLen )
                localSb.Length = sbLen = strLen;

            for( int j = 0; j < sbLen; j++ )
            {
                if( localSb[j] != str[j] )
                {
                    localSb.Length = j;
                    break;
                }
            }

            return localSb;
        },
        ( localSb ) =>
        {
            lock( finalListLock )
            {
                finalList.Add( localSb.ToString() );
            }
        } );

    return GetCommonPrefix( finalList );
}

GetCommonPrefixParallel () повышает в два раза по сравнению с GetCommonPrefix () при большом количестве строк и значительных длинах строк. На небольших массивах с короткими строками GetCommonPrefix () работает немного лучше. Я тестировал на MacBook Pro Retina 13 ''.

Answer 2

Топ ответ может быть улучшен, чтобы игнорировать регистр:

.TakeWhile(s =>
  {
      var reference = s.First();
      return s.All(d => string.Equals(reference, d, StringComparison.OrdinalIgnoreCase));
  })