Find the Index of the First Occurrence in a String

Лёгкая№28фиксированный размер

Даны две строки: длинная и короткий образец. Верни индекс, с которого образец впервые встречается в длинной строке, или -1, если не встречается. Наш пример: «bad» в «ecbbadfg» — ответ 3.

28 Find the Index of the First Occurrence in a StringРазбор · 1×

Пример: haystack = «ecbbadfg», needle = «bad». У каждой буквы есть код, a = 1, b = 2, …; окно хранит сумму своих кодов.

0e1c2b3b4a5d6f7g53221467needlebadsum–target–
ещё не дошлиокновходящая буквауходящая буква, ложная тревогавышло из окнаобразец

В образце 3 буквы: каждое окно длиной 3

01/35
сначала · назад · пуск · шаг
Скорость
1function strStr(haystack, needle):
2 m = len(needle)
3 target = sum of code(c) for c in needle // a = 1, …
4 sum = 0
5 for right from 0 to len(haystack) - 1:
6 sum = sum + code(haystack[right])
7 if right >= m:
8 sum = sum - code(haystack[right - m])
9 if right >= m - 1 and sum == target:
10 start = right - m + 1
11 if haystack[start .. right] == needle:
12 return start
13 return -1
состояние
m
3
target
–
sum
–
right
–
start
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Окно всегда длиной с образец и сдвигается на одну букву, поэтому проверяется каждое место, где мог бы начаться образец, и первое — первым.
  2. Если суммы разные, то и буквы разные: такое окно отбрасывается за O(1). Сумма обновляется, как текущая сумма: один код входит, один выходит.
  3. Равные суммы ещё не значат равные буквы («cbb» и «bad» обе дают 7), поэтому окно с нужной суммой всё равно сравниваем по буквам.

Сложность

Время: суммы стоят O(n + m), и ещё O(m) за каждое окно с совпавшей суммой. Если ложных тревог мало, выходит O(n + m); в худшем случае, когда нужная сумма почти у каждого окна, O(n · m). Память O(1).

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.