|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
09.01.2018, 12:53 | #1 |
Новичок
Джуниор
Регистрация: 09.01.2018
Сообщений: 1
|
Алгоритм поиска подстроки с разрывами C++, STL
Доброго времени суток!
Стоит нетривиальная проблема. Есть строка user_string, есть подстрока to_del. Необходимо с минимальным ущербом (минимальное число удалений символов) удалить из user_string символы так, что бы подстрока to_del перестала в ней существовать в любом виде (даже с разрывами) Что значит разрывы? "uy45nbj387h" - в этом user_string подстрокой будет даже "y8h", поскольку символы присутствуют в такой последовательности, пусть и на расстоянии друг от друга Реализовать смог только очень жадную штуку за О(user_string.size()^2), которая действительно получает "чистую строку", но очень сильно режет её размер - решение не нужно такое, тк на выходе нам нужна максимальная длина последовательности. Кто может помочь? |
09.01.2018, 13:40 | #2 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Навскидку - ориентированный граф, построенный из всех возможных комбинаций символов подстроки в исходной строке. Удалить некоторые вершины так, что бы в каждом оставшемся несвязном графе длина пути была меньше количества символов подстроки. Наверно начал бы с удаления тех вершин, в которые сходится максимальное количество ребер
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм поиска подстроки | 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 |