Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > C++ > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 09.01.2018, 13:53   #1
growfood
Новичок
 
Регистрация: 09.01.2018
Сообщений: 1
Репутация: 10
Печаль Алгоритм поиска подстроки с разрывами C++, STL

Доброго времени суток!

Стоит нетривиальная проблема. Есть строка user_string, есть подстрока to_del. Необходимо с минимальным ущербом (минимальное число удалений символов) удалить из user_string символы так, что бы подстрока to_del перестала в ней существовать в любом виде (даже с разрывами)

Что значит разрывы?
"uy45nbj387h" - в этом user_string подстрокой будет даже "y8h", поскольку символы присутствуют в такой последовательности, пусть и на расстоянии друг от друга

Реализовать смог только очень жадную штуку за О(user_string.size()^2), которая действительно получает "чистую строку", но очень сильно режет её размер - решение не нужно такое, тк на выходе нам нужна максимальная длина последовательности.

Кто может помочь?
growfood вне форума   Ответить с цитированием
Старый 09.01.2018, 14:40   #2
Аватар
Модератор
Заслуженный модератор
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Адрес: Северодонецк.ua
Сообщений: 17,940
Репутация: 6285
По умолчанию

Навскидку - ориентированный граф, построенный из всех возможных комбинаций символов подстроки в исходной строке. Удалить некоторые вершины так, что бы в каждом оставшемся несвязном графе длина пути была меньше количества символов подстроки. Наверно начал бы с удаления тех вершин, в которые сходится максимальное количество ребер
__________________
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Требуется разработчик мультимедийных сервисов (качество поиска) C++ и STL BessonovaAnastasiy Работа на постоянной основе - Вакансии 1 30.07.2012 18:57
Алгоритм поиска подстроки shwan Помощь студентам 2 23.04.2012 23:49
STL алгоритм сорт Progsenya Общие вопросы C/C++ 2 09.09.2010 23:38
Функция поиска и замены подстроки в строке типа PChar Son Помощь студентам 9 19.04.2010 16:06
алгоритм рабина-карпа(поиск подстроки) kristy42 Помощь студентам 0 03.11.2009 19:41


19:00.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru