В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

pro.algorithms

1792 membersпожаловаться на группу
2020 December 15

АJ

Артём Jin in pro.algorithms
Mikail Bagishov
По описанию скорее разделяй и властвуй, чем бинпоиск :)

но по-моему тут есть простое жадное решение
много раз слышал, читал на вики и не понял... В чём соль принципа "разделяй и властвуй"? Это условная рекурсия?
источник
20:33пожаловаться#1

АJ

Артём Jin in pro.algorithms
Mikail Bagishov
Ну это должно работать по идее
значит я рукожоп, которые запорол реализацию.
источник
20:33пожаловаться#2

АJ

Артём Jin in pro.algorithms
готовлюсь к муниципальному этапу олимпы по инфе)
источник
20:34пожаловаться#3

MB

Mikail Bagishov in pro.algorithms
Там гораздо проще решение
источник
20:34пожаловаться#4

MB

Mikail Bagishov in pro.algorithms
Вот давай посмотрим на тот символ, который надо вырезать
источник
20:34пожаловаться#5

MB

Mikail Bagishov in pro.algorithms
Что ты можешь сказать про те k символов, которые идут перед ним?
источник
20:34пожаловаться#6

АJ

Артём Jin in pro.algorithms
они равны?
источник
20:35пожаловаться#7

MB

Mikail Bagishov in pro.algorithms
Да, они равны первым k символам маленькой строки
источник
20:35пожаловаться#8

АJ

Артём Jin in pro.algorithms
ну срез из s до него равен соотвест. срезу t
источник
20:35пожаловаться#9

MB

Mikail Bagishov in pro.algorithms
Окей, пусть теперь для какого-то k первые k символов первой строки не равны первым k символам какой-то другой строки. Что ты можешь сказать про позицию ответа?
источник
20:36пожаловаться#10

АJ

Артём Jin in pro.algorithms
можно по одному сравнивать, я так делал, по времени не прошло.
источник
20:36пожаловаться#11

MB

Mikail Bagishov in pro.algorithms
А как сравнивал?
источник
20:36пожаловаться#12

АJ

Артём Jin in pro.algorithms
Mikail Bagishov
Окей, пусть теперь для какого-то k первые k символов первой строки не равны первым k символам какой-то другой строки. Что ты можешь сказать про позицию ответа?
она в нём
источник
20:36пожаловаться#13

АJ

Артём Jin in pro.algorithms
Mikail Bagishov
А как сравнивал?
брал индекс по s и если убрать элемент, сравнивал строки
источник
20:37пожаловаться#14

АJ

Артём Jin in pro.algorithms
Артём Jin
она в нём
ответ среди первых k
источник
20:37пожаловаться#15

MB

Mikail Bagishov in pro.algorithms
А теперь представь, что то же самое произошло с каким-то суффиксом
источник
20:38пожаловаться#16

MB

Mikail Bagishov in pro.algorithms
То есть последние k символов различаются.
источник
20:38пожаловаться#17

АJ

Артём Jin in pro.algorithms
тоже самое, ответ среди них
источник
20:38пожаловаться#18

MB

Mikail Bagishov in pro.algorithms
То есть в пересечении любого такого префикса и любого такого суффикса, так?
источник
20:39пожаловаться#19

АJ

Артём Jin in pro.algorithms
да
источник
20:39пожаловаться#20