Реализовать strstr (поиск подстроки)
Условие
Реализуйте функцию поиска первого вхождения подстроки в строку (аналог strings.Index).
Сигнатура
func strstr(haystack, needle string) int
Требования
- Вернуть индекс первого вхождения needle в haystack
- Вернуть -1, если needle не найден
- Если needle пустая строка, вернуть 0
Примеры
Вход: haystack = "hello", needle = "ll"
Выход: 2
Вход: haystack = "aaaaa", needle = "bba"
Выход: -1
Вход: haystack = "hello", needle = ""
Выход: 0
Комментарии (1)
Ответ сгенерирован нейросетью и может содержать ошибки
Поиск подстроки
Задача: найти первое вхождение needle в haystack.
Алгоритм Brute Force
Шаг 1: Если needle пустая, return 0 Шаг 2: Если needle длиннее haystack, return -1 Шаг 3: Для каждой позиции i в haystack (от 0 до len-len(needle)): Проверяем совпадает ли подстрока haystack[i:i+len(needle)] с needle Если совпадает, return i Шаг 4: Если не найдена, return -1
Пример
haystack = hello, needle = ll
Позиция 0: haystack[0:2] = he != ll Позиция 1: haystack[1:3] = el != ll Позиция 2: haystack[2:4] = ll == ll -> return 2
Сложность
Time: O(n*m) где n=len(haystack), m=len(needle) Space: O(1)
Граничные случаи
- needle = пусто -> return 0
- haystack = пусто, needle не пусто -> return -1
- needle == haystack -> return 0
- needle в конце haystack -> работает правильно
- needle не найдена -> return -1
Оптимизация
Для очень больших строк использовать KMP или Rabin-Karp алгоритмы с O(n+m) временем.
Для обычных случаев Brute Force достаточно хорош благодаря short strings и современным CPU.
Варианты сравнения
Вариант 1: Сравнение слайсов
if haystack[i:i+len(needle)] == needle
Вариант 2: Побайтовое сравнение
for j in range(len(needle)):
if haystack[i+j] != needle[j]:
break
if j == len(needle)-1:
return i
Вариант 2 может быть быстрее благодаря early exit.