Find the First Occurrence in a String

+10

Даны две строки: haystack и needle. Верните индекс в haystack, с которого начинается первое вхождение needle, считая с 0. Если needle ни разу не встречается в haystack, верните -1. Реализуйте поиск самостоятельно, а не вызывайте встроенный поиск подстроки, например find или indexOf.

Функция

strStr(haystack: string, needle: string) → integer

haystackstring: текст для поиска
needlestring: строка, которую нужно найти
Возвращаетinteger: индекс, с которого начинается первое вхождение needle, или -1, если его нет

Ограничения

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
Обе строки содержат только строчные буквы английского алфавита.
needle может быть длиннее, чем haystack. Тогда она не может в нём содержаться, и ответ — -1.

Примеры

Ввод: haystack = "bananarama"needle = "ana"
Вывод: 1
Пояснение: Буквы с индексами 1, 2 и 3 образуют ana. Вторая копия начинается с индекса 3 и перекрывает первую, но ответом является первая копия, поэтому это 1.

Ввод: haystack = "pineapple"needle = "apples"
Вывод: -1
Пояснение: apple начинается с индекса 4, а строка поиска заканчивается сразу после него, поэтому последней s в искомой строке не с чем совпасть. Полной копии apples нет, поэтому ответ — -1.

Ввод: haystack = "abcabcabd"needle = "abcabd"
Вывод: 3
Пояснение: Попытка с индекса 0 совпадает с пятью буквами, abcab, затем встречает c, тогда как в искомой строке требуется d. Подходящее совпадение начинается с индекса 3 и заканчивается последней d.

+16 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

Сравнивать needle в каждой начальной позиции правильно, но медленно, когда совпадения почти удаются: длинное частичное совпадение, которое завершается неудачей почти в самом конце, отбрасывается, а при следующем старте снова считывается большая часть тех же букв. Алгоритм Кнута — Морриса — Пратта сохраняет эту работу. Таблица, построенная только по needle, показывает, какую часть неудачного частичного совпадения всё ещё можно использовать, поэтому сканирование никогда не движется назад по haystack и завершается за O(n + m).

Проверьте каждую начальную позицию

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

Идея

Обозначим длины haystack через n, а needle — через m. Копия needle может начинаться с любого индекса от 0 до n-m. Проверяй эти позиции слева направо. Для каждой позиции сравнивай needle с haystack буква за буквой и останавливайся при первом несовпадении. Первая позиция, в которой совпадают все m букв, и будет ответом; проверка слева направо гарантирует, что это первое вхождение.

Последняя возможная позиция — n-m, поскольку копия, начинающаяся позже, выйдет за конец haystack. Та же граница учитывает ситуацию, когда needle длиннее haystack: проверять нечего, и цикл завершится возвратом -1.

Затраты становятся заметны, когда совпадает большинство букв. Возьмём haystack из 50 000 букв a и needle из 24 999 букв a, за которыми следует b. В каждой из 25 001 позиций проверяются 25 000 букв, прежде чем алгоритм дойдёт до b. В итоге получается более 6 × 10^8 сравнений, а ответ — -1.

Алгоритм

Пусть n и m — длины haystack и needle.
Для каждого start от 0 до n-m установите j равным 0.
Пока j < m и haystack[start + j] равен needle[j], увеличивайте j.
Если j достиг m, значит, совпали все символы: верните start.
Если ни одно значение start не подошло, верните -1.

def strStr(haystack, needle):
    n, m = len(haystack), len(needle)
    for start in range(n - m + 1):
        j = 0
        while j < m and haystack[start + j] == needle[j]:
            j += 1
        if j == m:
            return start
    return -1

Кнут — Моррис — Пратт

Идея

Посмотрите, что отбрасывает метод грубой силы. При поиске abcabd в abcabcabd попытка с индекса 0 совпадает с abcab, а затем завершается неудачей. Эти пять букв заканчиваются на ab, и ab — это также начало образца. Поэтому после несовпадения две буквы следующей подходящей попытки уже совпали, и можно продолжить с того же места в строке.

Граница строки — это более короткий префикс, который также является суффиксом, например ab в abcab. До начала поиска постройте таблицу lps, где lps[i] — длина наибольшей границы needle[0..i]. Для abcabd это [0, 0, 0, 1, 2, 0]. Таблица зависит только от образца, и её можно построить тем же циклом сопоставления, запущенным для образца относительно него самого.

Затем просканируйте строку один раз и отслеживайте k — количество букв образца, совпавших на данный момент. Если следующая буква равна needle[k], увеличьте k на единицу. Если нет, присвойте k значение lps[k-1] и снова сравните ту же букву — до совпадения или до тех пор, пока k не станет равным 0. Переход к границе никогда не пропускает вхождение: любое вхождение, начинающееся внутри неудачной попытки, должно начинаться с границы уже сопоставленной части, а сначала проверяется самая длинная граница. Когда k достигает m, вхождение начинается с позиции i-m+1.

Почему алгоритм линейный: k увеличивается не более чем на единицу для каждой буквы строки, а каждый откат уменьшает его. Значит, откатов не может быть больше, чем увеличений, поэтому сканирование занимает не более 2n шагов, а построение таблицы — не более 2m.

Алгоритм

Постройте lps: при k = 0 для каждого i от 1 до m-1 возвращайтесь назад, присваивая k = lps[k-1], пока k > 0 и needle[i] не совпадает с needle[k]; если они совпадают, увеличьте k; сохраните lps[i] = k.
Сбросьте k до 0 и пройдите по строке haystack с индексом i.
Пока k > 0 и haystack[i] не совпадает с needle[k], установите k = lps[k-1].
Если haystack[i] равен needle[k], увеличьте k.
Если k равен m, верните i-m+1. Если цикл завершится, верните -1.

def strStr(haystack, needle):
    m = len(needle)
    # lps[i]: length of the longest proper prefix of needle[0..i] that is also its suffix
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and needle[i] != needle[k]:
            k = lps[k - 1]
        if needle[i] == needle[k]:
            k += 1
        lps[i] = k

    k = 0  # how many letters of needle are matched so far
    for i, ch in enumerate(haystack):
        while k > 0 and ch != needle[k]:
            k = lps[k - 1]  # fall back to the longest border, never move i back
        if ch == needle[k]:
            k += 1
        if k == m:
            return i - m + 1
    return -1

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

Большинство ошибок возникает в конце стога сена или внутри цикла отката.

Допускают, чтобы start увеличивался до n-1 вместо n-m. Если конец стога сена совпадает с началом иглы, сравнение выходит за пределы haystack, из-за чего Python, Java, Rust и Swift выдают ошибку индекса.
Забывают, что игла может быть длиннее стога сена. При беззнаковых длинах, таких как size_t в C++ или usize в Rust, n-m не может быть отрицательным: C++ преобразует результат в огромное число, а Rust вызывает панику в отладочной сборке. Сначала проверьте m > n или выполняйте вычисления со знаковыми целыми числами.
Записывают откат KMP как if, а не как while. При поиске aaa в aabaa для символа b нужны два отката: с 2 до 1, а затем до 0. Если остановиться после одного, k останется равным 1, хотя b ни с чем не совпадает, и вы сообщите о копии по индексу 2, которой не существует.
При несовпадении в KMP перемещают индекс стога сена назад. Меняется только k. Возврат i к предыдущим значениям возвращает худшую оценку O(n · m).
Возвращают позицию конца совпадения или индекс, отсчитываемый от 1. Ответ — это начало, отсчитываемое от 0. Строки в Lua и R начинаются с 1, поэтому перед возвратом вычтите 1.
Объявляют strStr на верхнем уровне в PHP. PHP не различает регистр в именах функций, поэтому имя конфликтует со встроенной функцией strstr. Поэтому в заготовке PHP функция помещена в собственное пространство имён.

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

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

Проверка каждой начальной позиции в худшем случае занимает время O(n · m), где n и m — длины строки haystack и строки needle, и требует дополнительной памяти O(1). Алгоритм Кнута — Морриса — Пратта работает за время O(n + m) и требует O(m) памяти для своей таблицы, независимо от того, какие используются буквы.

Как работает таблица префиксов KMP?

Для каждого префикса образца таблица хранит длину его наибольшего собственного префикса, который также является суффиксом. После несовпадения, когда совпали k букв, эти k букв являются префиксом образца, а lps[k-1] указывает, сколько из них могут начать следующее возможное вхождение. Для aabaaab таблица имеет вид [0, 1, 0, 1, 2, 2, 3].

Почему бы не использовать встроенные методы find или indexOf?

В производственном коде следует использовать встроенный поиск: он протестирован и работает быстро. Интервьюеры задают эту задачу, чтобы посмотреть, как ты напишешь соответствующий цикл с правильными границами, а в обычном дополнительном вопросе спрашивают, как избежать худшего случая O(n · m). Худший случай для встроенного поиска зависит от языка и версии библиотеки, поэтому такой ответ не подходит для этого дополнительного вопроса.

Можешь решить это с помощью хеширования вместо KMP?

Да, с помощью алгоритма Рабина — Карпа. Вычислите хеш иглы и скользящий хеш каждого окна из m букв в строке, обновляя его за постоянное время по мере перемещения окна. Сравнивайте буквы одну за другой только в том случае, если хеши совпадают. Ожидаемая сложность такого алгоритма — O(n + m), но большое количество коллизий хешей может увеличить её почти до O(n · m).

Python

def strStr(haystack, needle):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

haystack = "bananarama"
needle = "ana"

Ожидается