Задача на поиск подстроки

@geniy12784 · Регистрация: 16.08.2022

Студворк — интернет-сервис помощи студентам

Дана строка S, состоящая из строчных и заглавных букв английского алфавита. Необходимо найти кратчайшую ее подстроку, содержащую хотя бы раз каждую букву, которая встречается в строке S. Буквы «a» и «A» считаются разными, иными словами регистр буквы важен

Подстрока строки S — это строка, состоящая из нескольких последовательных букв из строки S. Например, строки «cab», «b» и «abacaba» являются подстроками строки «abacaba», а строки «aa», «abc» - нет

Входные данные
В первой строке вводится целое число N (1≤N≤100000) — длина строки S
Во второй строке вводится сама строка S, состоящая из строчных и заглавных букв английского алфавита

Выходные данные
Выведите длину кратчайшей подходящей подстроки

Примеры
входные данные
4
lamp
выходные данные
4
входные данные
3
GgG
выходные данные
2
входные данные
7
AbAcAbA
выходные данные
3

@Red white socks · 16.08.2022, 13:01

Python
1
2
3
4
5
6
7
8
9
s = input()
length_min = len(s)
 
for left in range(len(s)):
    for right in range(left, len(s):
        if len(set(s)) == len(set(s[left:right+1])):
            length_min = min(length_min, right + 1 - left)
            break
print(length_min)

Добавлено через 4 минуты
Алгоритм неоптимальный, но вдруг прокатит

@avdivo · 16.08.2022, 16:37

Red white socks,
Предлагаю небольшую оптимизацию:

Python
1
2
3
4
5
6
7
8
9
10
s = input()
length_min = len(s)
length_substr = len(set(s))
 
for left in range(len(s)-length_substr):
    for right in range(left+length_substr, len(s)):
        if length_substr == len(set(s[left:right])):
            length_min = min(length_min, right - left)
            break
print(length_min)

@Red white socks · 16.08.2022, 20:01

avdivo, ну это так, слону дробина. Все равно О(N^2). Тут нужен минимум О(N log N).
Вот этот код на порядок быстрее, но он тоже квадратичный

Python
1
2
3
4
5
6
7
8
9
10
11
indexes ={}
for x in set(s):
    indexes.setdefault(x, [_.start() for _ in re.finditer(x, s)] )
left, right = 0, max(min(x) for x in indexes.values())
current_min = right - left + 1
while right < len(s):
    n = min([_ for _ in indexes.get(s[left:left+1]) if _ > left], default = len(s))
    right = max(right, n)
    left += 1
    current_min = min (current_min, right - left + 1)
print(current_min)

Его можно уменьшить до N log N, если в словаре индексов вместо списка использовать сортированный список или кучу.

@Red white socks · 17.08.2022, 12:49

Ок. Займемся теперь расчетами.
Инициализируем тестовую строку:

Python
1
2
3
4
5
6
7
from random import seed, choice
alphabet = 'abcdefghijklmnopqrstuvwxyz'
alphabet += alphabet.upper()
#s = input()
len_s = 100000
seed(42)
s =''.join([choice(alphabet) for _ in range(len_s)])

Первоначальный код уходит в астрал, что неудивительно, поскольку его сложность O(n^3). O(n^2) итераций в цикле и O(n) на сравнение длин множеств.

Посмотрим на следующий вариант. Его сложность O(n^2), причем скорость выполнения обратно пропорциональна длине алфавита, чем больше различных символов в строке, тем быстрее выполняется расчет.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import re
from time import time
 
start = time()
indexes ={}
for x in set(s):
    indexes.setdefault(x, [_.start() for _ in re.finditer(x, s)] )
left, right = 0, max(min(x) for x in indexes.values())
current_min = right - left + 1
while right < len(s):
    next_pos = min([_ for _ in indexes.get(s[left:left+1]) if _ > left], default = len(s))
    right = max(right, next_pos)
    left += 1
    current_min = min (current_min, right - left + 1)
print(current_min)
print(f'Время выполнения {time()-start:.3f}с')
 
#100
#Время выполнения 9.891с

Неплохо, но мы знаем как улучшить)
Используем SortedList. Кстати, узнал о замечательной библиотеке sortedcontainers https://grantjenks.com/docs/sortedcontainers/, так что уже время потрачено не зря)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import re
from time import time
from sortedcontainers import SortedList
 
start = time()
indexes ={}
for x in set(s):
    indexes.setdefault(x, SortedList([_.start() for _ in re.finditer(x, s)]+[len(s)]) )
 
left, right = 0, max(min(x) for x in indexes.values())
current_min = right - left + 1
while right < len(s) - 1:
    next_pos = next(indexes.get(s[left:left+1]).irange(left, inclusive=(False, True)))
    right = max(right, next_pos)
    left += 1
    current_min = min (current_min, right - left + 1)
print(current_min)
print(f'Время выполнения {time()-start:.3f}с')
 
#100
#Время выполнения 0.360с

Это алгоритм уже сложности N log N, поскольку на поиск позиции в массиве тратит log N времени.
Но самое интересное, что пока вносил изменения, то в голове появилось решение уже с обычными списками и со временем O(N)!

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import re
from time import time
 
start = time()
indexes, pointers ={},{}
for x in set(s):
    indexes.setdefault(x, [_.start() for _ in re.finditer(x, s)] +[len(s)] )
    pointers.setdefault(x,0)
 
left, right = 0, max(min(x) for x in indexes.values())
current_min = right - left + 1
while right < len(s):
    left_char = s[left:left+1]
    pointers[left_char] += 1
    next_pos = indexes[left_char][pointers[left_char]]
    right = max(right, next_pos)
    left += 1
    current_min = min (current_min, right - left + 1)
print(current_min)
print(f'Время выполнения {time()-start:.3f}с')
 
#100
#Время выполнения 0.151с

Тут еще видно, что вместо словаря указателей можно использовать очереди и это еще должно ускорить выполнение. Но с меня уже, пожалуй, хватит. Если кто хочет - может проверить...
Вот вроде и всё. Спасибо за внимание.

Добавлено через 1 час 1 минуту
Ну и напоследок, очень поучительная история о слепоте и хождении по кругу)
Что только не использовали для индексов) И список, и сортированный список и кучу предлагал. В конце до очереди додумался. И возникает вопрос, зачем нам здесь очередь, если можно взять обычный итератор. Но так итератор нам сразу и дает re!
Просто удивительно, как готовое решение все пытался во что-то обернуть...

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
start = time()
indexes = {}
for x in set(list(s)):
    indexes.setdefault(x, re.finditer(x, s) )
 
left, right = 0, max(next(x).start() for x in indexes.values())
current_min = right - left + 1
while right < len(s):
    left_char = s[left:left+1]
    try:
        next_pos = next(indexes[left_char]).start()
    except:
        next_pos = len(s)
    right = max(right, next_pos)
    left += 1
    current_min = min (current_min, right - left + 1)
print(current_min)
print(f'Время выполнения {time()-start:.3f}с')

На 100К разницы нет (за исключением чистоты исполнения), но на 1М последняя версия примерно на 10% быстрее.
Не знаю, как остальные, а я очень впечатлен уроком от этой непритязательной школьной задачи.

@avdivo · 17.08.2022, 13:04

Red white socks,
Впечатляет! Очень интересно, спасибо.

Новые блоги и статьи Все статьи Все блоги /
1С: Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .
Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .

@geniy12784 0 / 0 / 0 Регистрация: 16.08.2022 Сообщений: 2

	Задача на поиск подстроки 16.08.2022, 10:33. Показов 6139. Ответов 5 Метки нет (Все метки) Дана строка S, состоящая из строчных и заглавных букв английского алфавита. Необходимо найти кратчайшую ее подстроку, содержащую хотя бы раз каждую букву, которая встречается в строке S. Буквы «a» и «A» считаются разными, иными словами регистр буквы важен Подстрока строки S — это строка, состоящая из нескольких последовательных букв из строки S. Например, строки «cab», «b» и «abacaba» являются подстроками строки «abacaba», а строки «aa», «abc» - нет Входные данные В первой строке вводится целое число N (1≤N≤100000) — длина строки S Во второй строке вводится сама строка S, состоящая из строчных и заглавных букв английского алфавита Выходные данные Выведите длину кратчайшей подходящей подстроки Примеры входные данные 4 lamp выходные данные 4 входные данные 3 GgG выходные данные 2 входные данные 7 AbAcAbA выходные данные 3 0

@avdivo 303 / 213 / 112 Регистрация: 03.12.2016 Сообщений: 409
	17.08.2022, 13:04
	Red white socks, Впечатляет! Очень интересно, спасибо. 0