Войти Регистрация
Алгоритмы

115. Вхождения запроса с одной опечаткой

Сложная

Даны строки pattern и text из строчных латинских букв. Окно — подстрока text длины len(pattern).

Верните по возрастанию все начала окон, которые отличаются от pattern не больше чем в одной позиции. Вставки и удаления не считаем, только замену символа.

В работе: Поиск в логе запросов Яндекс Карт названия улицы, набранного с одной опечаткой: «тверская» и «тверскаа» — одно и то же.

Пример 1

Ввод
pattern = "abc"
text = "abcxbcabd"
Вывод
[0, 3, 6]

Окна с 0 (точное), 3 («xbc», одна замена) и 6 («abd»).

Пример 2

Ввод
pattern = "aa"
text = "a"
Вывод
[]

Шаблон длиннее текста — окон нет.

Ограничения

  • 1 ≤ длина pattern
  • 0 ≤ длина text ≤ 10⁵
  • Только строчные латинские буквы
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def find_with_one_typo(pattern, text):
СтрокиZ-функцияцельO(n)

Источник: наша задача на данных Яндекса. Условие пересказано своими словами.