|
0 / 0 / 0
Регистрация: 14.05.2017
Сообщений: 19
|
|
Уничтожить подпоследовательность в строке09.01.2018, 11:51. Показов 625. Ответов 16
Метки нет (Все метки)
Столкнулся с такой проблемой, вводится строка S и строка T. Нужно убрать наименьшее количество букв в строке S, чтобы в ней не встречалась строка T в порядке слева направо(если T=aba, но в строке aaab не встречается T, а в строке aaba встречается). Попытки были, но не знаю как сделать наименьшее возможное количество убранных букв
Спасибо за помощь.
0
|
|
| 09.01.2018, 11:51 | |
|
Ответы с готовыми решениями:
16
|
|
230 / 199 / 71
Регистрация: 21.10.2016
Сообщений: 449
|
|||||||||||
| 09.01.2018, 13:14 | |||||||||||
|
Так что ли?
0
|
|||||||||||
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
|
| 09.01.2018, 13:19 | |
|
1
|
|
|
0 / 0 / 0
Регистрация: 14.05.2017
Сообщений: 19
|
|
| 09.01.2018, 18:26 [ТС] | |
|
Строки S и T могут быть какими удобно + нужно убрать минимальное количество букв. Гораздо хитрее.
0
|
|
|
|
|
| 10.01.2018, 10:11 | |
|
По моему представлению здесь нужно плясать от расстояния Хэмминга. Причем так, чтобы (с аналитической точки зрения) при удалении символов из S, ее части плохо схлопывались в T.
Добавлено через 18 секунд А так, да, развеселая задачка.
0
|
|
|
2744 / 2053 / 507
Регистрация: 17.02.2014
Сообщений: 9,473
|
||||||
| 10.01.2018, 15:21 | ||||||
|
мне думается так:
0
|
||||||
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
|
| 10.01.2018, 15:50 | |
|
код пишет b
что это значит?
0
|
|
|
2744 / 2053 / 507
Регистрация: 17.02.2014
Сообщений: 9,473
|
|
| 10.01.2018, 17:51 | |
|
что эта минимальная часть подстроки T, которую нужно убрать в строке S, чтобы нельзя было найти целую T в S.
0
|
|
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
|
| 10.01.2018, 21:16 | |
|
убираем первую b - остается aaaba, убираем вторую b - aabaa, оба варианта, очевидно, неправильные
0
|
|
|
2744 / 2053 / 507
Регистрация: 17.02.2014
Сообщений: 9,473
|
|
| 11.01.2018, 08:57 | |
сразу 2 b нужно убирать
0
|
|
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
|
| 11.01.2018, 12:01 | |
|
Достаточно убрать одно а же
0
|
|
|
2744 / 2053 / 507
Регистрация: 17.02.2014
Сообщений: 9,473
|
|
| 11.01.2018, 12:12 | |
|
0
|
|
|
0 / 0 / 0
Регистрация: 14.05.2017
Сообщений: 19
|
||
| 15.01.2018, 10:52 [ТС] | ||
|
Я задал вопрос из-за того, что мой код(с перебором все вариантов(например всех n-подряд букв(n - строка T)) занимал много времени(был криво реализован). Ограничение по времени: одна секунда. Строка до миллиона символов, дело не в неправильности решения, а в "неоптимизированности". Переборное решение занимает много времени, а другого я придумать не смог. Проблема состоит только во времени. Это решение не совсем перебор, но работает долго.
0
|
||
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
|
| 15.01.2018, 10:56 | |
|
JustHacker,
так ты свое решение то выложи, может подумаем и сделаем быстрее
0
|
|
|
0 / 0 / 0
Регистрация: 14.05.2017
Сообщений: 19
|
|
| 15.01.2018, 11:00 [ТС] | |
|
Перебором если только(типа S=aaba, t=ab, перебираем для каждых двух подряд идущих букв, и так пока не уничтожим). Для больших строк нужна оптимизация.
0
|
|
|
2744 / 2053 / 507
Регистрация: 17.02.2014
Сообщений: 9,473
|
|
| 15.01.2018, 11:33 | |
|
Так я из t делаю всевозможные комбинации подстрок, слева направо и потом, считаю, сколько этих кусочков входит в s. Затем, выбираю минимальный кусочек.
0
|
|
|
15 / 15 / 1
Регистрация: 15.01.2018
Сообщений: 42
|
|||||||||||
| 16.01.2018, 10:29 | |||||||||||
|
Вот решения(правильные, на java не получилось)
![]() С++: Кликните здесь для просмотра всего текста
Python: Кликните здесь для просмотра всего текста
0
|
|||||||||||
| 16.01.2018, 10:29 | |
|
Помогаю со студенческими работами здесь
17
Уничтожить вектор Уничтожить зеркало
Уничтожить стек Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так:
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347
Основана на STM32F303RBT6.
На борту пять. . .
|
Символьное дифференцирование
igorrr37 13.02.2026
/ *
Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет
значение производной при заданном х
Логарифм записывается как: (x-2)log(x^2+2) -. . .
|
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
|
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу,
и светлой Луне.
В мире
покоя нет
и люди
не могут жить в тишине.
А жить им немного лет.
|
|
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила»
«Время-Деньги»
«Деньги -Пуля»
|
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога
Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога
Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
|