Точный набор совпадений для ключевых слов в тексте ⇐ Python

[Anonymous]

В тексте есть несколько ключевых слов и их начальная/конечная позиция. Ключевые слова могут частично перекрываться, например. "что-то" -> "что-то"/"что-то"/"вещь":

Код: Выделить всё

keywords_occurences = {
"key_1": [(11, 59)],
"key_2": [(24, 46), (301, 323), (1208, 1230), (1673, 1695)],
"key_3": [(24, 56), (1208, 1240)],
...
}

Мне нужно выбрать одну позицию для каждого ключевого слова, чтобы они не пересекались. В этом случае решение:

Код: Выделить всё

key_1: 11-59
key_2: 301-323     (or 1673-1695, it does not matter)
key_3: 1208-1240

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

Выглядит как своего рода проблема с «точным набором попаданий», но я не могу найти описание алгоритма.

Подробнее здесь: https://stackoverflow.com/questions/123 ... ds-in-text