12. кп24-370

Текстовый файл 24-367.txt содержит только заглавные буквы латинского алфавита и точки. Назовём словом непустую непрерывную последовательность букв, ограниченную точками по обеим сторонам. Найдите минимальную длину подстроки, содержащую не менее K = 12000 слов, содержащих букву Q. В ответе укажите длину найденной строки. Например, в строке «AB...QCE.FQ..GQX.» есть три слова содержат букву Q: «.QCE.», «.FQ.»  и «.GQX.». В этом случае при K = 2 минимальную длину 8 имеет подстрока «.QCE.FQ.».
Ваш ответ Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!

Скрыть/Показать редактор кода (Python) time 1000 ms

Выберите правильный ответ, либо введите его в поле ввода

Комментарий учителя

     
Разбор

🔍 Разбор примера пошагово

Шаг 1. Анализ строки
Строка: AB...QCE.FQ..GQX.
Индексы: 0 1 2 3 4 5 6 7 8 9 10... 13... 16
         A B . . . Q C E . F Q . . G Q X .

Точки находятся на позициях: 2, 3, 4, 8, 11, 12, 16

Шаг 2. Находим все слова (между точками)
№ Между точками Слово Есть Q?
1 позиции 0-1 AB ❌
2 позиции 2-3 (пусто) -
3 позиции 3-4 (пусто) -
4 позиции 4-8 QCE ✅
5 позиции 8-11 FQ ✅
6 позиции 11-12 (пусто) -
7 позиции 12-16 GQX ✅

Найдено 3 слова с Q: QCE, FQ, GQX

Шаг 3. Запоминаем позиции слов с Q (с точками!)
Слово Точка перед Точка после Подстрока с точками
QCE 4 8 .QCE.
FQ 8 11 .FQ.
GQX 12 16 .GQX.
Шаг 4. Ищем минимальное окно для K=2

Проверяем все возможные окна из 2 последовательных слов с Q:

Окно 1→2 (QCE и FQ):
• Начало: точка перед QCE = позиция 4
• Конец: точка после FQ = позиция 11
• Подстрока: text[4:12] = ".QCE.FQ."
• Длина: 11 - 4 + 1 = 8 ✅
Окно 2→3 (FQ и GQX):
• Начало: точка перед FQ = позиция 8
• Конец: точка после GQX = позиция 16
• Подстрока: text[8:17] = ".FQ..GQX."
• Длина: 16 - 8 + 1 = 9
Минимальная длина: 8

💻 Решение с регулярными выражениями

import re

f = open("24-367.txt")
k = 12000
text = f.read()

# Regex находит ПОЗИЦИИ всех слов с Q
words_with_q = []
for m in re.finditer(r'\.([A-PR-Z]*Q[A-PR-Z]*)', text):
    words_with_q.append((m.start(), m.end()))

# Python перебирает все окна и находит минимум
min_length = float('inf')
for i in range(len(words_with_q) - k + 1):
    length = words_with_q[i + k - 1][1] - words_with_q[i][0] + 1
    min_length = min(min_length, length)

print(min_length)

Разбор регулярного выражения

Часть паттерна Значение
\. Точка перед словом (экранированная)
([A-PR-Z]*Q[A-PR-Z]*) Слово с Q: любые буквы кроме Q, потом Q, потом снова любые буквы
[A-PR-Z] Любая буква от A до Z, КРОМЕ Q
⚠️ Важно: Паттерн НЕ включает точку после слова, но m.end() возвращает позицию ПОСЛЕ последнего символа совпадения — это как раз позиция точки после слова!

Как работает код на примере

Для строки: AB...QCE.FQ..GQX. 
Итерация 1: найдено '.QCE'
  m.start() = 4 (позиция точки перед QCE)
  m.end() = 8 (позиция ПОСЛЕ E, то есть точка после QCE)
  words_with_q.append((4, 8))

Итерация 2: найдено '.FQ'
  m.start() = 8 (точка перед FQ)
  m.end() = 11 (точка после FQ)
  words_with_q.append((8, 11))

Итерация 3: найдено '.GQX'
  m.start() = 12
  m.end() = 16
  words_with_q.append((12, 16))

words_with_q = [(4, 8), (8, 11), (12, 16)]
Поиск минимального окна для k=2:

i=0: Окно от слова 0 до слова 1
  start_pos = words_with_q[0][0] = 4
  end_pos = words_with_q[1][1] = 11
  length = 11 - 4 + 1 = 8
  min_length = 8

i=1: Окно от слова 1 до слова 2
  start_pos = words_with_q[1][0] = 8
  end_pos = words_with_q[2][1] = 16
  length = 16 - 8 + 1 = 9
  min_length = 8 (не обновляется)

Результат: 8
✅ Формула длины: end_pos - start_pos + 1
Почему +1? Потому что нужно включить ОБЕ граничные точки в подсчёт.

Альтернативное решение БЕЗ регулярных выражений

Более понятный и надёжный способ — работать с позициями точек напрямую:

f = open("24-367.txt")
k = 12000
text = f.read()

# Шаг 1: Находим ВСЕ позиции точек в тексте
dot_positions = []
for i in range(len(text)):
    if text[i] == '.':
        dot_positions.append(i)

# Альтернатива через list comprehension:
# dot_positions = [i for i, c in enumerate(text) if c == '.']

# Шаг 2: Проверяем слова между соседними точками
words_with_q = []

for i in range(len(dot_positions) - 1):
    # Берём две соседние точки
    start_dot = dot_positions[i]
    end_dot = dot_positions[i + 1]

    # Извлекаем слово между ними (без точек)
    word = text[start_dot + 1 : end_dot]

    # Проверяем: непустое И содержит Q
    if word and 'Q' in word:
        # Запоминаем позиции точек (не самого слова!)
        words_with_q.append((start_dot, end_dot))

# Шаг 3: Ищем минимальное окно методом скользящего окна
min_length = float('inf')

for i in range(len(words_with_q) - k + 1):
    # Берём K последовательных слов, начиная с i-го
    start_pos = words_with_q[i][0]           # Точка перед первым словом
    end_pos = words_with_q[i + k - 1][1]    # Точка после k-го слова

    # Длина подстроки (включая обе точки)
    length = end_pos - start_pos + 1

    # Обновляем минимум
    if length < min_length:
        min_length = length

print(min_length)

Пошаговый разбор на примере

Шаг 1: Находим все точки
text = "AB...QCE.FQ..GQX."
dot_positions = [2, 3, 4, 8, 11, 12, 16]
Шаг 2: Анализируем слова между точками
i=0: между точками 2 и 3
  word = text[3:3] = "" (пусто) → пропускаем

i=1: между точками 3 и 4
  word = text[4:4] = "" (пусто) → пропускаем

i=2: между точками 4 и 8
  word = text[5:8] = "QCE"
  'Q' in "QCE" = True ✅
  words_with_q.append((4, 8))

i=3: между точками 8 и 11
  word = text[9:11] = "FQ"
  'Q' in "FQ" = True ✅
  words_with_q.append((8, 11))

i=4: между точками 11 и 12
  word = text[12:12] = "" (пусто) → пропускаем

i=5: между точками 12 и 16
  word = text[13:16] = "GQX"
  'Q' in "GQX" = True ✅
  words_with_q.append((12, 16))

Результат: words_with_q = [(4, 8), (8, 11), (12, 16)]
Шаг 3: Ищем минимальное окно (k=2)
i=0: окно от слова 0 до слова 1
  start_pos = 4
  end_pos = 11
  length = 11 - 4 + 1 = 8 ✅

i=1: окно от слова 1 до слова 2
  start_pos = 8
  end_pos = 16
  length = 16 - 8 + 1 = 9

min_length = 8

📊 Сравнение подходов

Критерий С регулярками Без регулярок
Скорость Быстрее (оптимизированный поиск) Медленнее (перебор всех символов)
Понятность Требует знания regex Более наглядно для новичков
Надёжность Нужно правильно составить паттерн Меньше шансов ошибиться
Гибкость Легко изменить критерий поиска Нужно переписывать условия

⚠️ Частые ошибки

Ошибка 1: Забыть +1 при вычислении длины
length = end_pos - start_pos → неправильно!
length = end_pos - start_pos + 1 → правильно!
Ошибка 2: Использовать паттерн с двумя точками r'\.([A-Z]*Q[A-Z]*)\.'
Такой паттерн пропустит перекрывающиеся слова (когда одна точка разделяет два слова с Q)
Ошибка 3: Не проверять, что слово непустое
Между двумя точками подряд .. слова нет!
Ошибка 4: Неправильный индекс при извлечении слова
word = text[start_dot:end_dot] → включает точки!
word = text[start_dot+1:end_dot] → правильно!

✅ Проверка решения

Для файла 24-367.txt с K = 12000:

Правильный ответ: 645835

Программа должна:

  • Найти около 18539 слов с буквой Q
  • Перебрать примерно 6540 окон (18539 - 12000 + 1)
  • Найти минимальное окно длиной 645835 символов

🎯 Выводы

  • Метод скользящего окна — оптимальный алгоритм для таких задач
  • Важно правильно определить границы подстроки (включая обе точки)
  • Формула длины: end_pos - start_pos + 1
  • Можно использовать как regex, так и простой перебор — оба подхода работают
  • Сложность алгоритма: O(n) для поиска слов + O(n) для поиска минимума = O(n)
Обсуждения (0)
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Решения (0)

Решения:

Нет доступных решений