时间戳

首页 > 解决方案 > 使用oracle sql查找最小非重复序列

sql - 使用oracle sql查找最小非重复序列

问题描述

考虑一个由字母组成的序列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'从位置 1aa开始，然后是位置 2aa 

    DATA    LENGTH
    ag       2
    ct       2
    gc       2

标签： sqloraclesequence

解决方案

查找字符串的所有子字符串，然后计算它们以查看其中有多少重复并排除任何不唯一的子字符串，然后找到每个字符串具有最小长度的子字符串集：

所以，如果你有测试数据：

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;

哪个输出：

身份证 | 价值 | 子串
-: | :----------- | :--------
 1 | 阿加加 | 插科打诨      
 2 | aaggcct | 吨        
 3 | aaggcctt | GC       
 3 | aaggcctt | 抄送       
 3 | aaggcctt | ct       
 3 | aaggcctt | 银       
 3 | aaggcctt | 啊       
 3 | aaggcctt | tt       
 3 | aaggcctt | gg       
 4 | aaagggcccttt | ct       
 4 | aaagggcccttt | GC       
 4 | aaagggcccttt | 银

db<>在这里摆弄

推荐阅读