1 Тема от EMLI_93

  • EMLI_93
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-10-31
  • Сообщений: 13

Тема: Игра - поиск слов

Два первоклассника играют в игру - поиск слов. Один из них загадывает слово и прячет его среди случайных букв, назовем это строкой A. Второй должен найти позицию этого слова по данной ему подсказке, в виде всех букв из этого слова (с учетом повторений), назовем это строкой B. Искомым словом в строке A является наименьшая по длине подстрока, которая содержит все буквы строки B в любом порядке. Если таких подстрок несколько, то искомым словом считается, то которое встречается первым. Первоклассники играют честно и поэтому слово обязательно присутствует в строке A. Надо помочь первоклассникам и написать программу, которая будет производить такой поиск и выдавать первую встречающуюся позицию.

ссылка на задачу http://olymp.krsu.edu.kg/GeneralProblem … ormat=html

как решать?

2 Ответ от EMLI_93

  • EMLI_93
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-10-31
  • Сообщений: 13

Re: Игра - поиск слов

задача не решаеться просто , нужен алгоритм

3 Ответ от MBo

  • MBo
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-10-05
  • Сообщений: 52

Re: Игра - поиск слов

Полагаю, что нужные символы могут перемежаться ненужными, хотя в задаче и в примерах это явным образом не указано.
Словарь маленький - это хорошо. Заводим два целочисленных массива, индексированных словарём (типа гистограммы). Один Wanted - заполняем из искомой строки (например, для строки aaab он будет выглядеть как [3,1,0,0...]), второй Current. Теперь нам нужно найти минимальное окно, в котором содержатся все символы искомой строки. Пусть два индекса указывают на начало и конец текущего окна. Количество найденных полезных символов Useful := 0
Сдвигаем конец вправо.
с = S[EndIndex]
Если новый символ не из нужных (Wanted[с] = 0), ничего больше не делаем на этом шаге, сдвигаем конец дальше, иначе:
Увеличиваем соответствующий элемент Current[c]
Важный момент: увеличиваем Useful в том случае, если Current[c] не превышает Wanted[с]
Если Useful равно длине искомой строки, то двигаем начало вправо, пока это возможно (т.е. начальный символ не из нужных, или соотв. элемент Current больше Wanted)
Проверяем, минимально ли получившееся окно

Сложность линейная O(Length(A)), память - O(размер словаря)

4 Ответ от EMLI_93

  • EMLI_93
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-10-31
  • Сообщений: 13

Re: Игра - поиск слов

Можете реализацию  написать, чтоб понятливой было

5 Ответ от Aliraza21

  • Aliraza21
  • Участник
  • Неактивен
  • Зарегистрирован: 2014-12-20
  • Сообщений: 1

Re: Игра - поиск слов

Что есть фигура - объединение, пересечение? Некоторые задачи с наборами прямоугольников рассматриваются в книге Препарата, Шеймос

Get Braindumps demos Testking 220-802 passguide with 100% success testking.us Our high quality keiseruniversity