Как найти одинаковую подстроку в массиве строк?

Рейтинг: 1Ответов: 2Опубликовано: 22.03.2023

Имеется массив строк:

[
    "D:\\src\\files\\folder/5.3.231/file.exe",
    "D:\\src\\files\\folder/5.1.1/file.exe",
    "D:\\src\\files\\folder/4.1/sub/file55.exe"
]

Нужно найти подстроку, которая бы была частью каждой строки массива с позиции 0 (с самого начала).

c#
Источник: Stack Overflow на русском

Ответы

▲ 3Принят

Это задача называется Longest common prefix, решить её можно следующим образом:

public string LongestCommonPrefix(string[] strs)
{
    if (strs == null || strs.Length == 0)
        return "";

    return CommonPrefix(strs, 0, strs.Length - 1);
}

private string CommonPrefix(string[] strs, int start, int end)
{
    if (start == end)
        return strs[start];

    int middle = (start + end) / 2;

    var left = CommonPrefix(strs, start, middle);
    var right = CommonPrefix(strs, middle + 1, end);
    return ConquerString(left, right);
}

private string ConquerString(string left, string right)
{
    int currentSmallest = Math.Min(left.Length, right.Length);
    for (int i = 0; i < currentSmallest; i++)
    {
        if (left[i] != right[i])
            return left.Substring(0, i);
    }
    return left.Substring(0, currentSmallest);
}

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

▲ 0

Благодаря названию задачи от @Kalmankantaja нашёл более изящный вариант на просторах интернета:

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