0

Задача: даны две строки S и T. Нужно найти их общую подстроку наибольшей длины. По условиям обе строки имеют одинаковую длину L (1≤L≤100000) и состоят только из строчных латинских букв. Гарантируется, что строки имеют хотя бы одну общую букву.

Я решил следующим образом:

var s = Console.ReadLine();
var t = Console.ReadLine();
var best = string.Empty;
for (int start = 0; start < s.Length; start++)
for (int length = 1; start + length <= s.Length; length++)
{
    var substring = s.Substring(start, length);
    if (t.Contains(substring) && substring.Length > best.Length)
        best = substring;
}
Console.WriteLine(best);

Но есть проблема - это неэффективно. Как можно сделать по-другому? Например, используя linq или же убрать один внешний цикл. Я плох в алгоритмах, а в гугле только такое решение.

1

1 ответ 1

2

Решение по алгоритму с использованием хеширования, по ссылке от @Akina, будет выглядеть примерно так.

static string LargestCommonSubstring(string left, string right)
{
    if (left == right) 
        return left;

    for (int length = left.Length - 1; length > 1; length--)
    {
        HashSet<string> set = new();
        for (int offset = 0; offset <= left.Length - length; offset++)
        {
            set.Add(left.Substring(offset, length));
        }
        for (int offset = 0; offset <= right.Length - length; offset++)
        {
            string substring = right.Substring(offset, length);
            if (set.Contains(substring))
                return substring;
        }
    }

    // оптимизация для односимвольной подстроки
    char[] chars = left.Distinct().OrderBy(x => x).ToArray();
    foreach (char c in right)
    {
        if (Array.BinarySearch(chars, c) >= 0)
            return c.ToString();
    }

    return null;
}
2
  • будет выглядеть примерно так Если не ошибаюсь, здесь хэши считаются за квадратичное время, а эффективное решение подразумевает rolling хэш. И проверка всех длин тоже не фонтан - итого получается куб вместо nlogn
    – MBo
    2 фев 2022 в 9:16
  • @MBo к сожалению, я не вижу пути решить это эффективнее используя только .NET классы. Если бы реально нужна была производительность, я бы использовал спаны и векторы и что-то получше полного перебора, например идти на увеличение и каждую последующую подстроку, которая длиннее на 1 символ искал бы среди найденных предыдущих, используя их как префиксы или что-то подобное. Что-то типа индексации, не уверен как это финально может выглядеть. Так что можно считать, что хэширование - это просто, но не лучшее решение, на мой взгляд.
    – aepot
    2 фев 2022 в 9:56

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.