Copy-paste detector есть в PMD:
pmd.sourceforge.net/pmd-5.0.1/cpd.html (не нашел сходу нормального описания на их сайте; когда-то видел статью про то, как он устроен: там суффиксный массив).
Если нужен именно алгоритм, то за O(N log N) (или, если постараться, O(N)) в худшем случае можно использовать
суффиксный массив,
суффиксное дерево или
суффиксный автомат (осторожно, статьи ориентированы на спортивное программирование, стиль кода может быть непривычным).
Пожалуй, проще всего работать с суффиксным массивом: это просто все суффиксы строки, упорядоченные в лексикографическом порядке (конечно, сами суффиксы хранятся не как строки, а как индексы начала). Для всех пар соседних суффиксов можно быстро найти LCP (наибольший общий префикс). Пусть дана минимальная длина (назовем ее L) искомых подстрок. Если в суффиксном массиве нашлись K последовательных (в лексикографическом порядке) суффиксов таких, что LCP любых двух соседних не меньше L, то LCP их всех есть подстрока исходной строки, входящая в нее хотя бы K раз. Используя эту идею, за O(N log N) можно, например, найти все подстроки длины L, встречающиеся хотя бы K раз (хотя это проще сделать хешами, как предложил
mihaildemidoff). Наверно, можно аналогично перебирать подходящие строки в порядке убывания длины или количества вхождений. Но наверно это удобнее делать суффиксным деревом.
Наверно, прямо при построении суффиксного дерева можно для каждой вершины найти количество вхождений соответствующей ей подстроки. Таким образом, мы найдем вообще для каждой подстроки количество ее вхождений. Но чтобы получилось O(N), а не O(N^2) данных, подстроки будут разбиты на группы (соответствующие вершинам дерева) с одинаковым количеством вхождений, и все произойдет за O(N). Того же самого можно (проще в реализации и сложнее в понимании) добиться и суффиксным автоматом (он в некотором смысле двойственен суффиксному дереву). Такой конструкции, наверно, достаточно для решения поставленной задачи в любой разумной конкретной формулировке.
