выберите строки с самой длинной подстрокой строки

Question

Позвольте мне описать проблему, основанную на примере ниже. Допустим, есть строка «abc12345» (может быть любая !!!) и есть таблица mytable с колонкой mycolumn varchar (100).

Есть некоторые строки, которая заканчивается последним символом 5.
Есть некоторые строки, заканчивается с последними символами 45.
Есть некоторые строки, заканчивается с последними символами 345
Там нет строки, заканчивается с последними символами 2345.

В этом случае эти строки должны быть выбраны:

SELECT * FROM mytable WHERE mycolumn LIKE "%345" 

это потому, что «345» является самой длинной правой подстрока «abc12345», которые происходят s хотя бы один раз, как правая подстрока, по крайней мере, одной строки в столбце mycolumn. Любые идеи, как написать это в одном запросе? Спасибо.

Answer 1

Это грубый метод силы:

select t.* 
from (select t.*, 
      dense_rank() over (order by (case when mycolumn like '%abc12345' then 1 
               when mycolumn like '%bc12345' then 2 
               when mycolumn like '%c12345' then 3 
               when mycolumn like '%12345' then 4 
               when mycolumn like '%2345' then 5 
               when mycolumn like '%345' then 6 
               when mycolumn like '%45' then 7 
               when mycolumn like '%5' then 8 
             end) 
          ) as seqnum 
     where mycolumn like '%5' -- ensure at least one match 
     from t 
    ) t 
where seqnum = 1; 

Это то вдохновляет что-то вроде этого:

select t.* 
from (select t.*, max(i) over() as maxi 
     from t join 
      (select str, generate_series(1, length(str)) as i 
      from (select 'abc12345' as str) s 
      ) s 
      on left(t.mycolumn, i) = left(str, i) 
    ) t 
where i = maxi; 

Answer 2

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

• Написать агрегатный UDF LONGEST_SUFFIX_MATCH(col, str) в C (см пример в sql/udf_example.c в источнике данных MySQL, поиск avgcost)

• SELECT @longest_match:=LONGEST_SUFFIX_MATCH(mycol, "abcd12345") FROM mytbl; SELECT * FROM mytbl WHERE mycol LIKE CONCAT('%', SUBSTR("abcd12345", -@longest_match))

Если бы вы могли изменить структуру таблицы, я d o еще не имеет полного решения, но в первую очередь я бы добавил специальный столбец mycol_rev, полученный путем изменения строки (через функцию REVERSE()) и создать на ней ключ, а затем использовать этот ключ для поиска. Поставит полное решение, когда у меня есть момент.

Update:

Если вы можете добавить обращенную столбец с ключом на нем:

• использовать запрос в формате `SELECT, myrevcol FROM mytbl WHERE myrevcol НРАВИТСЯ CONCAT (SUBSTR (REVERSE ('$ search_string'), $ n), '%') LIMIT 1, выполняющий двоичный поиск по $ n в диапазоне от 1 до длины $ search_string, чтобы найти наибольшее значение $ n, для которого запрос возвращает строка
• SELECT * FROM mytbl WHERE myrevcol LIKE CONCAT (SUBSTR (REVERSE ('$ search_string'), $ found_n), '%')

Это решение должно быть очень быстрым, если у вас не слишком много строк, возвращающихся назад. У нас будет общее количество запросов O (log (L)), где L - длина строки поиска, каждая из которых является поиском B-дерева с чтением только одной строки, за которой следует другой поиск B-дерева с показанием индекса из только необходимых строк.

Answer 3

Интересная головоломка :)

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

В MySQL вам, вероятно, необходимо использовать либо генераторную серию, либо UDF. Другие предложили это уже.

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

select v, 
    reverse(
     substring(
     reverse(v) || '#' || reverse('abcdefg') 
     from '^(.*).*#\1.*' 
    )) res 
from table; 

Что она делает это:

• строит одну строку, совмещая строку и суффикс , Обратите внимание, мы отменяем их.
• мы помещаем # между важными строками, вам нужен символ, которого нет в вашей строке.
• выделит матч из регулярного выражения, используя substring, так что
  • начинается в начале строки ^
  • совпадает с любым количеством символов (.*)
  • могут иметь некоторые оставшиеся символы .*
  • сейчас мы находим #
  • сейчас, мы хотим, чтобы с той же строкой мы сопоставляли (.*), чтобы быть предварительно отправляется сразу после #. Таким образом, мы используем \1
  • и могут быть некоторые персонажи хвост .*
  • мы поменяем извлеченную строку

После того, как у вас есть длинный суффикс, найти максимальную длину, а затем найти все строки, имеющие суффикс этой длины тривиален.

SQLFiddle Использование PostgreSQL: