Найдите минимальную неповторяющуюся последовательность, используя oracle sql

Question

Рассмотрим последовательность, состоящую из букв a,g,c,t. Вы должны найти минимальную неповторяющуюся последовательность символов и их длину. Также обратите внимание, что неповторяющийся символ должен быть в последовательности.

Например, в последовательности 'aaggcct' ответ - минимальный неповторяющийся символ равен t, где t - наименее неповторяющийся набор символов, а длина - 1. Даже если aa,gg,cc,ag,gc,ct не повторяется, поскольку t наименее неповторяется с длиной 1, ответ - t. Когда я говорю, что t неповторяется, тогда в последовательности нет других t.

Для последовательности 'aaggcctt' один из ответов, например, aa,, является наименьшим -повторный набор символов. Даже если aag не повторяется, наименьшая неповторяющаяся длина равна 2, следовательно, это не рассматривается. Когда я говорю, что 'aa' не повторяется, в последовательности нет других aa. Полный ответ приведен ниже

    DATA    LENGTH
    ag       2
    gg       2
    ct       2
    cc       2
    aa       2
    tt       2
    gc       2

Еще один пример последовательности 'aaagggcccttt' здесь aa повторяется, следовательно, не в ответе. Когда я говорю, что 'aa' повторяется, потому что в 'aaa' есть два 'aa', смотрящих из положения 1 aa, а затем из положения 2 aa

    DATA    LENGTH
    ag       2
    ct       2
    gc       2

Answer 1

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

Итак , если у вас есть данные теста:

CREATE TABLE test_data ( id, value ) AS
  SELECT 1, 'agaga' FROM DUAL UNION ALL
  SELECT 2, 'aaggcct' FROM DUAL UNION ALL
  SELECT 3, 'aaggcctt' FROM DUAL UNION ALL
  SELECT 4, 'aaagggcccttt' FROM DUAL;

Тогда вы можете использовать:

WITH substrings ( id, value, length, pos ) AS (
  SELECT id,
         value,
         LENGTH( value ),
         1
  FROM   test_data
UNION ALL
  SELECT id,
         value,
         CASE pos
         WHEN 1
         THEN length - 1
         ELSE length
         END,
         CASE pos
         WHEN 1
         THEN LENGTH(value) - (length-2)
         ELSE pos-1
         END
  FROM   substrings
  WHERE  length > 1
  OR     pos > 1
),
non_repeats ( id, value, substring ) AS (
  SELECT id,
         MIN( value ),
         SUBSTR( value, pos, length )
  FROM   substrings s
  GROUP BY id, SUBSTR( value, pos, length )
  HAVING COUNT(*) = 1
)
SELECT id,
       value,
       substring
FROM   (
  SELECT id,
         value,
         substring,
         RANK() OVER ( PARTITION BY id ORDER BY LENGTH( substring ) ASC ) AS rnk
  FROM   non_repeats
)
WHERE  rnk = 1;

Какие выходы:

ID | VALUE        | SUBSTRING
-: | :----------- | :--------
 1 | agaga        | gag      
 2 | aaggcct      | t        
 3 | aaggcctt     | gc       
 3 | aaggcctt     | cc       
 3 | aaggcctt     | ct       
 3 | aaggcctt     | ag       
 3 | aaggcctt     | aa       
 3 | aaggcctt     | tt       
 3 | aaggcctt     | gg       
 4 | aaagggcccttt | ct       
 4 | aaagggcccttt | gc       
 4 | aaagggcccttt | ag       

дБ <> скрипка здесь

Answer 2

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

        WITH dna
         AS (SELECT value
                    ||'$' AS seq,
                    id
             FROM   test_data),
         iterator
         AS (SELECT column_value n,
                    id
             FROM   dna
                    cross join TABLE(Cast(MULTISET (SELECT LEVEL
                                              FROM   dual
                                              CONNECT BY LEVEL <= Length(seq)) AS
                                           sys.ODCINUMBERLIST))),
         target_data
         AS (SELECT Count(1)                             cnt,
                    Substr(dna2.seq, i1.n, i2.n)         data1,
                    Length(Substr(dna2.seq, i1.n, i2.n)) lngth,
                    dna2.id,
                    Replace(seq, '$', '')                value
             FROM   dna dna2,
                    iterator i1,
                    iterator i2
             WHERE  dna2.id = i1.id
                    AND dna2.id = i2.id
             GROUP  BY Substr(dna2.seq, i1.n, i2.n),
                       Length(Substr(dna2.seq, i1.n, i2.n)),
                       dna2.id,
                       seq
             HAVING Count(1) = 1)
    SELECT id,
           value,
           data1
    FROM   target_data td
    WHERE  lngth = (SELECT Min(lngth)
                    FROM   target_data td1
                    WHERE  td1.id = td.id)
    ORDER  BY id; 

Выходные данные

    ID  VALUE          DATA1
    1   agaga           gag
    2   aaggcct         t
    3   aaggcctt        cc
    3   aaggcctt        gc
    3   aaggcctt        ag
    3   aaggcctt        ct
    3   aaggcctt        gg
    3   aaggcctt        aa
    3   aaggcctt        tt
    4   aaagggcccttt    ct
    4   aaagggcccttt    ag
    4   aaagggcccttt    gc