Longest Common Substring

Q: Какова временная сложность алгоритма поиска наибольшей общей подстроки?

Решение с динамическим программированием работает за время O(n × m) и требует O(m) памяти при использовании одной строки. Продление от каждой пары начальных позиций в худшем случае занимает O(n × m × min(n, m)) . Суффиксный автомат обеспечивает сложность около O(n + m) ценой значительно более длинной программы.

Q: Как вернуть самую длинную общую подстроку?

Каждый раз, когда ячейка превосходит best , также записывай позицию i в s1 , где заканчивается этот блок. В конце подстрока — это best букв из s1 , заканчивающихся на этой позиции. Строгое сравнение «больше» позволяет сохранить первый найденный в s1 самый длинный блок.

СреднеДинамическое программирование

+10

Вам даны две строки: s1 и s2. Подстрока — это непрерывная последовательность букв из строки, например ork из clockwork. Найдите самую длинную подстроку, общую для s1 и s2, и верните её длину. Если в обеих строках нет ни одной общей буквы, ответ — 0.

Функция

longestCommonSubstring(s1: string, s2: string) → integer

s1string: первая строка
s2string: вторая строка
Возвращаетinteger: длина самого длинного блока букв, найденного в обеих строках

Ограничения

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 и s2 состоят из строчных букв английского алфавита.

Примеры

Ввод: s1 = "clockwork"s2 = "workshop"
Вывод: 4
Пояснение: work завершает clockwork и начинает workshop, поэтому это общая подстрока длиной 4, и более длинного фрагмента, который встречается в обоих, нет.

Ввод: s1 = "hammer"s2 = "harmed"
Вывод: 2
Пояснение: ha и me встречаются в обоих словах, но ни одна последовательность из трёх букв не встречается. В обоих словах буквы h, a, m, e расположены в таком порядке, но в слове harmed между a и m стоит r.

Дополнительный вопрос

Можете ли вы проверить, существует ли общая подстрока заданной длины L, примерно за O(n + m) с помощью скользящего хеша, а затем выполнить бинарный поиск по L?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Продлевать совпадение для каждой пары начальных позиций — значит перечитывать одни и те же буквы. Вместо этого посмотрим, где блок заканчивается: общий блок, заканчивающийся на s1[i] и s2[j], на одну букву длиннее блока, заканчивающегося на двух предшествующих им буквах, или пуст, если буквы различаются. Таблица этих длин дает ответ за время O(n × m).

Расширяйтесь от каждой пары начальных позиций

Верно, но не успевает на самых больших тестах

Идея

Каждая общая подстрока начинается в некоторой позиции i строки s1 и в некоторой позиции j строки s2. Для каждой пары двигайтесь вперёд, пока буквы совпадают, и считайте шаги; наибольшее количество шагов и будет ответом.

В повторяющемся тексте проходы получаются длинными. Когда обе строки состоят из 1000 копий a, каждый проход для пары позиций продолжается до конца более короткого суффикса: примерно 3.3 × 10^8 сравнений букв. Проход из (i, j) повторяет весь проход из (i+1, j+1), только на одну букву позже.

Алгоритм

Установите best = 0.
Для каждого i в s1 и каждого j в s2 установите k = 0.
Пока и i+k, и j+k находятся внутри своих строк и s1[i+k] == s2[j+k], увеличивайте k на 1.
Сохраните наибольшее значение k в best и верните его.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

Таблица длин блоков, заканчивающихся на каждой паре

Идея

Пусть run[i][j] — длина наибольшего общего фрагмента, который заканчивается ровно на s1[i-1] и s2[j-1]; в строке 0 и столбце 0 хранятся нули. Такой фрагмент должен содержать обе буквы. Если они различаются, общего фрагмента нет, и ячейка равна 0. Если они совпадают, фрагмент состоит из этой пары и фрагмента, который заканчивается на одну букву раньше в обеих строках: run[i-1][j-1] + 1. Каждая общая подстрока где-то заканчивается, поэтому ответ — наибольшая ячейка, где бы она ни находилась.

Для hammer и harmed буквы h дают 1, а буквы a увеличивают длину до 2, затем r прерывает фрагмент. Вторая m в hammer совпадает с m в harmed после несовпадения m и r, поэтому начинает фрагмент длины 1, а буквы e увеличивают его длину до 2. Ни одна ячейка не достигает 3.

Одно сравнение на ячейку: около миллиона для двух строк из 1000 букв, независимо от текста.

Алгоритм

Выдели для run n+1 строк и m+1 столбцов, заполни их нулями и установи best = 0.
Перебирай i от 1 до n, а внутри этого цикла — j от 1 до m, сравнивая s1[i-1] с s2[j-1].
При совпадении установи run[i][j] = run[i-1][j-1] + 1 и обнови best.
При несовпадении оставь в ячейке 0.
Верни best.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

Одна строка, обновляемая справа налево

Идея

Каждая ячейка считывает значение только из ячейки по диагонали сверху слева. Поэтому для таблицы можно использовать один массив run из m+1 чисел, если проходить по j справа налево: когда вы записываете значение в run[j], в ячейке run[j-1] всё ещё хранится значение для предыдущей буквы s1 — то есть значение из ячейки по диагонали.

При несовпадении теперь нужно явно записывать 0, потому что в ячейке всё ещё хранится число из предыдущей строки. Время работы остаётся равным O(n × m), а объём памяти сокращается примерно с 10^6 чисел до 1001.

Алгоритм

Создай массив run из m+1 нулей и установи best = 0.
Для каждой буквы ch в s1 перебирай j от m до 1.
Если ch == s2[j-1], установи run[j] = run[j-1] + 1 и обнови best.
Иначе установи run[j] = 0.
Верни best.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

Ловушки и крайние случаи

Возврат значения в последней ячейке. run[n][m] учитывает только блоки, которые заканчиваются на последних буквах обеих строк. Для abc и abd это 0, а для ab получается 2.
Копирование большего значения у соседней ячейки при несовпадении. Это правило для подпоследовательности, и оно позволяет блоку пропускать буквы: для hammer и harmed оно даёт 4 вместо 2.
Проход по единственной строке слева направо. Значение по диагонали перезаписывается до того, как вы его прочитаете, поэтому для a и aa получается 2.
Пропуск сброса в единственной строке. Длина для предыдущей буквы из s1 сохраняется и позже расширяет блок, которого там нет.
Проход по алгоритму полного перебора без проверки границ. Для zzzz и zz он читает данные за концом более короткой строки.

Частые вопросы3

В чем разница между наибольшей общей подстрокой и наибольшей общей подпоследовательностью?

Подстрока — это непрерывная последовательность букв; подпоследовательность сохраняет порядок, но может содержать пропуски. Для hammer и harmed длина наибольшей общей подстроки равна 2, а длина наибольшей общей подпоследовательности — 4 (hame). В таблицах несовпадение сбрасывает значение в ячейке подстроки до 0, но в ячейку подпоследовательности копируется большее из соседних значений.

Какова временная сложность алгоритма поиска наибольшей общей подстроки?

Решение с динамическим программированием работает за время O(n × m) и требует O(m) памяти при использовании одной строки. Продление от каждой пары начальных позиций в худшем случае занимает O(n × m × min(n, m)). Суффиксный автомат обеспечивает сложность около O(n + m) ценой значительно более длинной программы.

Как вернуть самую длинную общую подстроку?

Каждый раз, когда ячейка превосходит best, также записывай позицию i в s1, где заканчивается этот блок. В конце подстрока — это best букв из s1, заканчивающихся на этой позиции. Строгое сравнение «больше» позволяет сохранить первый найденный в s1 самый длинный блок.

def longestCommonSubstring(s1, s2):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

s1 = "clockwork"
s2 = "workshop"

Ожидаемый вывод

Longest Common Substring

Функция

Ограничения

Примеры

Подсказки

Решение

Расширяйтесь от каждой пары начальных позиций

Таблица длин блоков, заканчивающихся на каждой паре

Одна строка, обновляемая справа налево

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи