[pva]

В общем, придумал способ находить цитаты (и подписи, если считать их цитатами), второе приближение.

Задача №1: найти все репосты. Решение: ищем общую последовательность максимальной длины, помечаем, вырезаем, разделяем найденной частью один из списков на два. Для каждой получившихся частей повторяем задачу заново.

Задача №2: в 2-х списках строк найти общую последовательность максимальной длины. Решаем как задачу динамического программирования. Пусть список sample - тот, из которого ищем цитаты, text - тот в котором ищем. Управление: позиция в sample, с которой начинается цитата. Состояние: лучшая длина + начало цитаты, текущая длина.
Т.о. возможен однопроходной алгоритм, количество сравнений - N*M, где N и M - длины списков.
Если считать цитаты достаточно редкими, то можно уменьшить расходуемую память и ускорить обработку за счёт использования хеш-мапов строк на состояния.

Если требуется нечёткое сравнение, то строки предварительно обрабатываются канонанизатором (т.е. перекодируются, выкидываются части, не имеющие значения)

Вероятно можно переформулировать задачу так, чтобы на выходе сразу получался разбитый цитатами список.

Какие ещё могут быть варианты решения задачи?