Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

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

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

Купить рекламу на форуме - 42 тыс руб за месяц

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

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

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

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

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

Кто может помочь?
growfood вне форума Ответить с цитированием
Старый 09.01.2018, 13:40   #2
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

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


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм поиска подстроки 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 18:41