Поиск максимальной повторяющейся подстроки в символьной строке с помощью SQL

Формулировка задачи

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

Например, для символьной строки:
сabjrehwklhgfjrehwkyupolkoraclenmoracleppmicrosoftmmicrosoftumicrosoft
Результат должен быть:

Краткое описание алгоритма

В данной задаче мы будем использовать так называемый наивный подход. Наивный подход к задаче отыскания самой длинной повторяющейся подстроки для текстовой строки Y может быть основан на матрице совпадений M размерности N x N. Элементы этой матрицы определяются следующим образом:

Диагонали из смежных '1', за исключением главной, представляют повторения в строке Y. В нашем случае мы найдем все повторяющиеся подстроки и выберем те, которые встречаются ровно 2 раза.

Составление матрицы N x N

Для решения поставления задачи будем использовать диалект SQL Oracle. Для того чтобы код выглядел более чистым, будем выделять подзапросы в отдельные блоки с помощью оператора WITH.

Сначала определим нашу строку.

DEFINE STR = 'сabjrehwklhgfjrehwkyupolkoraclenmoracleppmicrosoftmmicrosoftumicrosoft';

Далее с помощью запроса line посчитаем сколько символов у нас всего в строке и сгенерируем последовательность от 1 до N. Оператор CONNECT BY помогает пробежаться по иерархии данных рекурсивно (в нашем случае есть только корень). Level - псевдостолбец, который определяет уровень иерархии.

WITH line AS (
SELECT LEVEL AS n
FROM DUAL
CONNECT BY LEVEL <= LENGTH('&STR'))

В результате выполнения этого запроса получим следующий результат:

На основе предыдущего запроса line, используя декартово произведение (Cross Join), сгенерируем матрицу M размерностью N x N, где i - индекс ячейки по горизонтали, j - индекс ячейки по вертикали, ceil_number - номер ячейки. ROWNUM - псевдостолбец, который нумерует строки в возвращаемом запросе.

matrix AS(
SELECT i.n AS i, j.n AS j, ROWNUM ceil_number
FROM line i, line j)

Наша матрица M будет иметь вид:

Согласно правилу определения элементов матрицы M составим запрос find_eq, который пропишет '1' в тех ячейках матрицы M, где Yi = Yj и i <> j.

find_eq AS(
SELECT ceil_number, i , j, 
    CASE
        WHEN SUBSTR('&STR', i, 1) = SUBSTR('&STR', j, 1) AND i <> j 
        THEN 1 
        ELSE 0
    END AS eq
FROM matrix)

Поиск подстроки максимальной длины

Далее с помощью запроса find_diagonals мы найдем все наши диагонали из '1'. Диагональ состоит из набора значений, где текущее значение стоит в ячейке (i, j), а следующее значение будет в ячейке (i + 1, j + 1).

find_diagonals AS(
SELECT cur.i AS first,  next.i AS last
FROM find_eq cur INNER JOIN find_eq next ON(cur.i - next.i = cur.j - next.j AND cur.i <> next.i)
WHERE cur.eq <> 0 AND next.eq <> 0 AND cur.I < next.I AND cur.J < next.J)

Для каждой из диагоналей выведем соответствующую подстроку, посчитаем длину полученной подстроки, а также сколько раз подстрока встречается в символьной строке. Функция REGEXP_COUNT считает количество вхождений темплейта в символьную строку.

get_all_subs AS(
SELECT first, last, SUBSTR('&STR', first, last - first + 1) S, REGEXP_COUNT('&STR',SUBSTR('&STR', first, last - first + 1)) count, LENGTH(SUBSTR('&STR', first, last - first + 1)) len
FROM find_diagonals)

Осталось найти только подстроки, которые встречаются ровно 2 раза и имеют максимальную длину.

result AS(
SELECT s, first, last
FROM get_all_subs subs
WHERE subs.count = 2 AND subs.len = (SELECT MAX(len) FROM get_all_subs WHERE count = 2))

Получим результат в следующем виде:

И последний запрос для красоты ответа.

SELECT r1.s AS "Подстрока", r1.first AS "Номер позиции начала 1", r2.first AS "Номер позиции начала 2"
FROM result r1 
INNER JOIN result r2 ON(r1.s = r2.s AND r1.first <> r2.first AND r1.first < r2.first);

Полученный результат

DEFINE STR = 'сabjrehwklhgfjrehwkyupolkoraclenmoracleppmicrosoftmmicrosoftumicrosoft';
WITH line AS (
SELECT LEVEL AS n
FROM DUAL
CONNECT BY LEVEL <= LENGTH('&STR')),

matrix AS(
SELECT i.n AS i, j.n AS j, ROWNUM ceil_number
FROM line i, line j),

find_eq AS(
SELECT ceil_number, i , j, 
    CASE
        WHEN SUBSTR('&STR', i, 1) = SUBSTR('&STR', j, 1) AND i <> j 
        THEN 1 
        ELSE 0
    END AS eq
FROM matrix),

find_diagonals AS(
SELECT cur.i AS first,  next.i AS last
FROM find_eq cur INNER JOIN find_eq next ON(cur.i - next.i = cur.j - next.j AND cur.i <> next.i)
WHERE cur.eq <> 0 AND next.eq <> 0 AND cur.I < next.I AND cur.J < next.J),

get_all_subs AS(
SELECT first, last, SUBSTR('&STR', first, last - first + 1) S, REGEXP_COUNT('&STR',SUBSTR('&STR', first, last - first + 1)) count, LENGTH(SUBSTR('&STR', first, last - first + 1)) len
FROM find_diagonals),

result AS(
SELECT s, first, last
FROM get_all_subs subs
WHERE subs.count = 2 AND subs.len = (SELECT MAX(len) FROM get_all_subs WHERE count = 2))

SELECT r1.s AS "Подстрока", r1.first AS "Номер позиции начала 1", r2.first AS "Номер позиции начала 2"
FROM result r1 
INNER JOIN result r2 ON(r1.s = r2.s AND r1.first <> r2.first AND r1.first < r2.first);