Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Андрей, 08 августа 2020 г. 18:52:02
     Есть ли какой глубокий смысл в фразе "Обе строки состоят только из символов английского алфавита и цифр" ?
  2  Георгий Шарушинский, 12 декабря 2019 г. 13:00:19
     Сдал задачу бором :)
  3  Тимофеев Александр Сергеевич, 03 декабря 2019 г. 23:42:35
     Странно, что я боялся сдавать эту задачу. Ведь тут маленькие ограничения и проходит substr + set
  4  Касым-Жомарт Кемелевич Токаев, 18 июля 2019 г. 18:41:53
     Люди ,использовать тут КМП глупо,при таких ограничениях даже самый примитивный метод пройдёт.Лучше найдите задачи такого типа на тимусе и тренируйтесь.
  5  Нуриев Наиль Дамирович, 16 апреля 2015 г. 18:13:45
     КМП + SET = accepted
  6  Ольмезов Константин Иванович, 25 февраля 2014 г. 22:21:12
     Судя по ограничениям и времени работы некоторых решений, в задаче допустим перебор. Слегка не интересно...
Надо было сделать ограничения побольше чтоб проходило только решение за O(N). У меня O(N) проскочило за 0.012 секунд, а в таблице лучших попыток видно и решения за 0,406.
  7  Павлов Михаил Валерьевич, 20 декабря 2013 г. 6:29:26
     Если правильно пользоваться STL функциями, задача на раз )))
  8  Зубакин Александр Сергеевич, 14 июля 2013 г. 14:09:18
     O(|s2| + |s1*s2|), где s2 - подстрока, а s1 - сама строка.
  9  Густавин Григорий, 13 сентября 2012 г. 12:10:52
     если тест: abababab abab ответ: 5 ?
     Совершенно верно
  10  Тест Тест Тест, 22 июня 2012 г. 20:35:30
     Прошло без КМП + set =)
     Да, здесь небольшие ограничения.
  11  Мырзакерей Мирас, 12 мая 2012 г. 21:57:37
     Немного КМП и процедур )
  12  Щербаков Александр Сергеевич, 16 января 2012 г. 17:02:54
     ababababa
aba
Ответ: 4
  13  НИКОПОЛЬ ЛУЧШЕ, 16 сентября 2011 г. 14:58:50
     Ура, прошло) Оказалось, нужно k в начале обнулить!
  14  Рокьян Эдгар, 13 февраля 2011 г. 18:36:32
     еле сдал=)
и все из-за невнимательности=(
  15  Згировский Андрей, 20 января 2011 г. 22:19:19
     мне кажется, для такой сложности ограничение на |a| должно быть <50000, а то просто в лоб написал и проходит( я думал сейчас придется что-нибудь в духе z-функции писать, а тут взяло и прошло :)
  16  Мехрдод ТРГИ[9"A" team], 18 июня 2009 г. 22:32:35
     У вас есть нормальная задача на сайте с КМП?? чтоб тока он проходил боше ничего а то тока ваши задачи меня вынуждают учить что-то))) вот если б была такая задача я-б вызубрил КМП!!!а так не интересно, читаю и забываю!!!))))
  17  Иванов Андрей Витальевич, 03 ноября 2007 г. 13:48:58
     алг Кнута-Мориса-Пратта
     Вовсе необязательно: ограничения слабые, поэтому подойдет и более простой алгоритм поиска подстроки.
  18  Гарри Поттер, 22 июня 2007 г. 10:04:41
     Спасибо, кажется, да :) Если задача получится, то точно да ;) А на второй вопрос, если можно?
     Если Вас интересует максимально возможная длина типа string в Delphi, то скажу, что его размер ограничен лишь памятью ЭВМ и может занимать, например, 128Mb что недопустимо во многих задачах, т.к. стандартное ограничение по памяти здесь 16Mb. Принципиально разный подход к типу string в Паскале и в Delphi, хотя суть работы с ними очень сходна. Но есть несколько отличий все же: 1е Вы отметили - это то, что в Delphi строка может быть очень длинной, ну а 2е - это то, что в Паскале ord(s[0]) - это длина строки, а в Delphi подобное обращение вообще не логично и недопустимо.
  19  Гарри Поттер, 21 июня 2007 г. 9:07:47
     Поясните, если можно, третий тест: циклический сдвиг аа равен аа и искать его вхождения второй раз не нужно, а 6 получается потому, что в ааааааа есть шесть пересекающихся вхождений аа? Или пересекающиеся вхождения не считаются, а ищется аа (3 раза), сдвигается в аа и ещё получается 3 раза? Надеюсь, вы поняли о чём я. Заранее спасибо. Ещё один вопрос. Из имеющихся здесь обсуждений понятно, что тип string при проверке не ограничен 255 символов, а какова его максимальная длина?
     Я Вас понял, конечно. Все пересечения считаются, т.е. строка "аа" входит в "ааааааа" 6 раз. Но после того, как происходит сдвиг строки "аа" мы получаем ту же "аа" и не рассматриваем ее. Нужно рассматривать только разные строки, которые могут получаться из исходной путем сдвига. Хотя это можно понять однозначно: ведь ясно, что рассматривая две подстроки с непустым пересечением мы имеем дело по сути с разными подстроками (несмотря на то, что строки равны могут быть). Ведь у подстроки есть еще позиция ее вхождения в оригинальную строку, тем подстрока и отличается от простой строки. А меня Вы поняли? :)
  20  Бобер Александр Дмитриевич, 15 марта 2007 г. 9:43:50
     1) Важна ли неприметная добавочка в условии о содержимом строк?
2) В 3-ем тесте цикл строки аа совпадает с самой строкой и его вхождения не учитываются, а если такая строка 101010?
     Задача абсолютно корректна и "неприметная добавочка" вносит некоторую однозначность и не заставляет задумываться о таких символах как символ с кодом 0 или перенос строки. Так что все верно.
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru