Pull to refresh

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

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

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

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

Подстрока

Номер позиции начала 1

Номер позиции начала 2

jrehwk

4

14

oracle

26

34

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

Алгоритм решения задачи

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

M_{ij} = \left\{ \begin{array}{lr} 1, & \text{ если } y_i = y_j\\ 0 & \text{ в остальных случаях } \end{array} \right.

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

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

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

Более подробно ознакомиться с оператором WITH

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

DEFINE STR = 'сabjrehwklhgfjrehwkyupolkoraclenmoracleppmicrosoftmmicrosoftumicrosoft';

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

Конструкця CONNECT BY для обработки иерархически связанных данных
WITH line AS (
SELECT LEVEL AS n
FROM DUAL
CONNECT BY LEVEL <= LENGTH('&STR'))

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

I

1

2

3

...

N

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

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

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

i

j

ceil_number

1

1

1

1

2

2

1

3

3

...

...

...

N

N

N*N

Согласно правилу определения элементов матрицы 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 считает количество вхождений темплейта в символьную строку.

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))

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

S

FIRST

LAST

jrehwk

4

9

jrehwk

14

19

oracle

26

31

oracle

34

39

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

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);
Полученный результат
SQL запрос целиком
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);
Tags:
Hubs:
You can’t comment this publication because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author’s username will be hidden by an alias.