Существует ли алгоритм максимального покрытия текста имеющимися подстроками?
Добрый день!
Подскажите, пожалуйста, имеется в наличии алгоритм (или хорошие идеи по реализации) решения следующей задачи: имеется строка текста (неопределенного размера, в большинстве случаев большая) и набор строк (в большинстве случаев достаточно большой). Необходимо на выходе дать комбинацию максимального непересекающегося покрытия текста совпадающими подстроками из набора, т.е. получить комбинацию при которой в тексте будет сведено к минимум кол-во областей для которых не нашли соответствующего слова из набора для "покрытия".
Скорее всего, их инструменты решают только первую часть задачи, а именно получение места вхождения каждой подстроки в строку. Для начала можно попытаться решить эту часть, как советует Армянское Радио или с помощью суффиксного массива.
Дальше задача сводится к поиску наилучшего покрытия отрезка непересекающимися отрезками. У меня не получилось быстро найти решение, но можно поробовать написать динамику.
На уровне идеи:
Допустим у нас есть n отрезков начала и концы которых обознацим b_i и e_i. Длинной покрытия будем называть сумму длин выбранных непересекающихся отрезков. Очевидно ее надо максимизировать. Обозначим как d[e_p] максимальную длину покрытия отрезками, для которых b_i > e_p. Отсортируем отрезки по e_i (по возрастанию). Тогда d[e_n] = 0. Посчитаем d[e_k] , если d[e_k + 1], d[e_k + 2], ...,d[e_n] уже посчитаны. Пусть b_s минимальное из начал отрезков такое, что b_s > e_k. Рассмотрим все отрезки пересекающиеся с началом принадлежащим s. S или один из этих отрезков входит в максимальное покрытие d[e_k]. Назовем их множество, вместе с s буквой L. Тогда d[e_k] = max(e_i - b_i + d[e_i]) по всем i из L.
Я не на 100% уверен, что это будет работать, но можете попробовать доказать.
К сожалению определение вхождений подтрок в текст - это лишь 1 этап. Финальная задача определить оптимальное распределение возможных вхождений для "сведения к минимуму кол-во областей для которых не нашли соответствующего слова из набора"
Средний
Простой
