Самая большая общая подстрока

30

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

  • Это может означать вывод пустой строки.
  • Если имеется несколько допустимых выходов, вы можете вывести любой из них. Вы не обязаны давать согласованный вывод для данного ввода, если вывод всегда действителен.
  • На входе всегда будет хотя бы одна строка, но может не быть непустой строки.
  • Все печатные символы ASCII могут появляться на входе. Вы можете предположить, что это единственные символы, которые появляются.
  • Вы можете получить ввод или произвести вывод любым из методов по умолчанию .
  • Стандартные лазейки не допускаются.
  • Это - чем меньше байтов кода, тем лучше.

Тестовые случаи:

[Inputs] -> [Valid outputs (choose one)]

["hello", "'ello"] -> ["ello"]
["very", "much", "different"] -> [""]
["empty", "", "STRING"] -> [""]
["identical", "identical"] -> ["identical"]
["string", "stRIng"] -> ["st", "ng"]
["this one", "is a substring of this one"] -> ["this one"]
["just one"] -> ["just one"]
["", "", ""] -> [""]
["many outputs", "stuptuo ynam"] -> ["m", "a", "n", "y", " ", "o", "u", "t", "p", "s"]
["many inputs", "any inputs", "ny iii", "yanny"] -> ["ny"]
["%%not&", "ju&#st", "[&]alpha_numeric"] -> ["&"]
Сара Дж
источник
2
@ Adám В этом вопросе задается самая длинная общая подпоследовательность , а не подстрока.
Ручка
1
Будут ли строки только буквенно-цифровыми, или буквенными, или только для печати-ascii?
Воплощение Неведения
@EmbodimentofIgnorance Все печатные символы ASCII могут появляться на входе.
Сара Джей
2
@ Шэгги Вообще-то нет. Если их можно различить, это undefinedозначает, что нет допустимой выходной строки. Если пустая строка (или любая другая строка) является допустимым выводом, утверждение о том, что допустимого вывода нет, неверно.
Сара Джей

Ответы:

8

Python 2 , 82 байта

f=lambda h,*t:h and max(h*all(h in s for s in t),f(h[1:],*t),f(h[:-1],*t),key=len)

Попробуйте онлайн!

Принимает входные данные Время ожидания для входов, где первая строка длинная.

Идея состоит в том, чтобы взять подстроки первых строк, hчтобы найти самую длинную, которая появляется во всех оставшихся строках t. Для этого мы рекурсивно разветвляемся на удаление первого или последнего символа h.


Python 2 , 94 байта

lambda l:max(set.intersection(*map(g,l)),key=len)
g=lambda s:s and{s}|g(s[1:])|g(s[:-1])or{''}

Попробуйте онлайн!

Более прямой метод. Вспомогательная функция gгенерирует множество всех подстрок s, а основная функция берет самую длинную в их пересечении.

XNOR
источник
8

Brachylog (v2), 3 9 байт

{sᵛ}ᶠlᵒtw

Попробуйте онлайн!

Полная программа. Ввод из стандартного ввода (в виде списка строк в стиле JSON), вывод в стандартный вывод.

объяснение

{sᵛ}ᶠlᵒtw
 s         Find a substring
  ᵛ          of every element {of the input}; the same one for each
{  }ᶠ      Convert generator to list
     lᵒt   Take list element with maximum length
        w  Output it

По-видимому, порядок разрыва связей sне тот, который есть почти во всем остальном в Brachylog, поэтому нам нужно вручную переопределить его, чтобы получить самый длинный вывод. (Это немного расстраивает: четыре дополнительных символа для переопределения, плюс два символа группировки, потому что Brachylog не анализирует два метапредиката подряд.)

Brachylog sне возвращает пустые подстроки, поэтому нам нужно немного обдумать это: вместо того, чтобы отправлять функцию (что обычно и делается), мы пишем полную программу, выводим ее на стандартный вывод. Таким образом, если есть общая подстрока, мы просто выводим ее, и все готово. Если нет общей подстроки, программа выдает ошибку - но она все равно ничего не печатает на стандартный вывод, таким образом, она выводит пустую строку, как и предполагалось

оборота ais523
источник
1
Я попробовал это с помощью ввода ["много inpuabts", "любые inabputs", "ny iabii", "yanabny"]. Я ожидал результатов ab и ny . Но только у результата A . Я делаю что-то неправильно ?
t-clausen.dk
1
Тьфу, кажется, я вспомнил порядок тай-брейка для s неправильно, и переопределение порядка разрыва связи довольно дорого в плане байтов. Делая это сейчас, тем не менее, потому что важно, чтобы ответ был правильным. Каким-то образом ни один из тестов, которые я пробовал, не заметил разницы.
ais523
1
@ ais523 Порядок создания sподстрок состоит в том, чтобы сначала дать все префиксы ввода (самый длинный сначала), затем отбросить первый и повторить
Kroppeb
5

Желе , 12 6 байт

Ẇ€f/ṫ0

Попробуйте онлайн!

Спасибо @JonathanAllan за сохранение 6 байтов!

Ник Кеннеди
источник
Я полагаю, Ẇ€œ&/Ṫḟ0что сделал бы работу и сохранил четыре байта, поскольку подстроки уже упорядочены по длине, следовательно, отфильтрованный результат будет; тогда остается только то, что при отсутствии совпадений tail выдает ноль, и, поскольку нам гарантированы списки символов, мы можем их просто отфильтровать.
Джонатан Аллан
Кроме того, я думаю, что œ&/может быть заменено f/здесь спасением другого
Джонатан Аллан
Я отправил запрос на извлечение (надеюсь) сделать результат сокращения пустого списка пустым списком (а не вызывать ошибку TypeError). Если это будет объединено, я считаю, что этот ответ может стать шестибайтовым Ẇ€f/ṛ/.
Джонатан Аллан
@JonathanAllan звучит хорошо. Спасибо за другие советы - надеюсь, вы были рады, что я включил их.
Ник Кеннеди
Да, моя причина этих комментариев состояла в том, чтобы позволить вам включить идеи в ваш пост.
Джонатан Аллан
5

Ruby 2.6, 76 59 54 байта

->a{*w=a;w.find{|r|w<<r.chop<<r[1..];a.all?{|s|s[r]}}}

Попробуйте онлайн! - Ruby 2.5 версия (56 байт)

Как?

Создайте список возможных совпадений, изначально установив исходный массив. Выполните итерацию по списку, и, если строка не совпадает, добавьте 2 новые строки в конец списка, обрезав первый или последний символ. В конце совпадение (в конце концов пустая строка) будет найдено.

Спасибо Кирилл Л за -2 байта и гистократ за еще -2

гигабайт
источник
4

R , 119 116 108 106 байт

function(S,`?`=nchar,K=max(?S),s=Reduce(intersect,lapply(S,substring,0:K,rep(0:K,e=K+1))))s[which.max(?s)]

Попробуйте онлайн!

Найдите все подстроки каждой строки, найдите пересечение каждого списка подстрок, затем, наконец, верните (одну из) самую длинную.

-3 байта благодаря Кириллу Л.

-8 байт, используя lapply вместо Map

-2 байта благодаря Кириллу Л. снова, удаляя брекеты

Giuseppe
источник
У меня нет времени, чтобы проверить, но, если я не ошибаюсь, 2 случая ncharдостаточно, чтобы что-то сохранить, объявив ncharунарным оператором.
Кирилл Л.
@KirillL. да, он короче на 2 байта. Благодарность! listАналогично, псевдоним дает нам -3 байта.
Джузеппе
Вы также можете сбросить фигурные скобки для другого -2
Кирилл Л.
@KirillL. Благодарность! Я немного волнуюсь, я собираюсь начать делать это с производственным кодом ...
Джузеппе
вот в чем проблема с игрой в гольф на языке, который вы используете каждый день
MickyT
4

05AB1E , 14 9 8 байтов

€Œ.«ÃéθJ

-6 байт благодаря @Adnan .

Попробуйте онлайн или проверьте все тесты .

Объяснение:

€Œ       # Get the substring of each string in the (implicit) input-list
       # Right-reduce this list of list of strings by:
    Ã    #  Only keep all the strings that are present in both list of strings
     é   # Sort by length
      θ  # And pop and push its last item
         # The substrings exclude empty items, so if after the reduce an empty list remains,
         # the last item will also be an empty list,
       J # which will become an empty string after a join
         # (after which the result is output implicitly)
Кевин Круйссен
источник
1
Я думаю, €Œ.«Ãõªéθдолжно работать на 9 байтов.
Аднан
@ Adnan Подождите, у нас есть снижение .. Как я пропустил это. : SI попробовал Å«Ã, но не понял, что я должен был бы использовать .«Ãвместо .. Спасибо!
Кевин Круйссен
1
На самом деле, я думаю, €Œ.«ÃéθJдолжно работать на 8.
Аднан
4

Zsh , 126 ... 96 байт

-3 байта для арифметики для, -6 байтов для неявного "$@"(спасибо roblogic), -5 байтов для удаления ненужных { }, -1 байт для краткой формы for, -1 байт для использования repeat, -1 байт для объединения for s ($b)с его телом, -13 байт изменив повторяющуюся петлю для некоторого рывка.

for l
eval a=\( \$l\[{1..$#l},{1..$#l}\] \)&&b=(${${b-$a}:*a})
for s ($b)(($#x<$#s))&&x=$s
<<<$x

Попробуйте онлайн! Попробуйте онлайн! Попробуйте онлайн!

Мы читаем все возможные подстроки в массив a, а затем устанавливаем bпересечение массивов aи b. Конструкция ${b-$a}будет заменять только $aна первой итерации: в отличие от расширения одного уровня ${b:-$a}, она не будет заменять, когда bона установлена, но пуста.

for l;                              # implicit "$@"

# === OLD ===
{
    a= i=                           # empty a and i
    repeat $[$#l**2]                # compound double loop using div/mod
        a+=($l[++i/$#l+1,i%$#l+1])  # append to a all possible substrings of the given line
#               1+i/$#l             # 1,1,1...,  1,1,2,2,2,... ...,  n,n
#                       1+i%$#l     # 1,2,3...,n-1,n,1,2,3,... ...,n-1,n
#       a+=( $l[       ,     ] )    # append that substring to the array
# === NEW ===
    eval a=\( \
        \$l\[{1..$#l},{1..$#l}\] \  # The {bracket..expansions} are not escaped
    \) &&
# ===     ===
    b=( ${${b-$a}:*a} )
#         ${b-$a}                   # if b is unset substitute $a
#       ${       :*a}               # take common elements of ${b-$a} and $a
#   b=(               )             # set b to those elements
}
for s ($b)                          # for every common substring
    (( $#x < $#s )) && x=$s         # if the current word is longer, use it
<<<$x                               # print to stdout
GammaFunction
источник
Как работает этот бит? a+=( $l[1+i/$#l,1+i%$#l] )
Роблогия
1
@roblogic Я думаю, что я объяснил это лучше, проверьте редактирование. Идея состоит в том, чтобы зацикливаться на n ^ 2 и использовать / и% вместо использования 2 вложенных forциклов
GammaFunction
1
Вы могли бы быть в состоянии сократить for l in "$@"просто for l;- это обман трюка
roblogic
Я должен сказать, что Zsh намного элегантнее, чем Bash. Там нет ничего аналогичного этому b=(${${b-$a}:*a})}
хорошему
1
Есть некоторые интересные вещи, которые вы можете сделать с этим, и это не так уж популярно. Это переводит меня, добавляя zsh-ответ на большинство вопросов, с которыми я сталкиваюсь. : P Если хочешь научиться зш, рекомендую man zshexpnи man zshparamособенно. Они всегда открыты при написании ответа.
GammaFunction
3

Haskell , 80 байт

import Data.List
f(x:r)=last$sortOn(0<$)[s|s<-inits=<<tails x,all(isInfixOf s)r]

Попробуйте онлайн!

Получить все суффиксы ( tails) первого слова xв списке и принять все префиксы ( inits) из этих суффиксов , чтобы получить все подстроки sиз x. Сохраните каждую из sэтих isInfixOf allстрок в оставшемся списке r. Сортировать эти подстроки по длине ( с использованием в (0<$)трик ) и вернуть последний.

Laikoni
источник
3

Сетчатка 0.8.2 , 48 байт

M&!`(?<=^.*)(.+)(?=(.*\n.*\1)*.*$)
O#$^`
$.&
1G`

Попробуйте онлайн! Объяснение:

M&!`(?<=^.*)(.+)(?=(.*\n.*\1)*.*$)

Для каждого суффикса первой строки найдите самый длинный префикс, который также является подстрокой всех других строк. Перечислите все эти суффиксные префиксы (то есть подстроки). Если нет подходящих подстрок, мы просто получим пустую строку, что нам и нужно.

O#$^`
$.&

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

1G`

Оставьте только первую, то есть самую длинную подстроку.

Нил
источник
Пусть n- количество строк аргумента. Тогда (?=(.*\n.*\1)*.*$)должно быть (?=(.*\n.*\1){n-1}.*$), не так ли? Прецедент:["very", "different", "much"] -> [""]
Маззи
1
@ mazzy Я не вижу проблемы: попробуйте онлайн!
Нил
это не проблема. с {n}вы можете удалить шаблоны начала и конца и сохранить , (.+)(?=(.*\n.*\1){n}если Retina позволяет писать nкороче(?<=^.*).*$
Mazzy
@ mazzy Я не могу в Retina 0.8.2, а в Retina 1 мне придется возиться с eval, который, вероятно, будет в любом случае длиннее.
Нил
3

TSQL-запрос, 154 байта

USE master
DECLARE @ table(a varchar(999)collate Latin1_General_CS_AI,i int identity)
INSERT @ values('string'),('stRIng');

SELECT top 1x FROM(SELECT
distinct substring(a,f.number,g.number)x,i
FROM spt_values f,spt_values g,@ WHERE'L'=g.type)D
GROUP BY x ORDER BY-sum(i),-len(x)

Попробуйте онлайн

Делается чувствительным к регистру, объявляя столбец «a» с сопоставлением, содержащим CS (с учетом регистра)

Разбивая все строки из 2540 начальных позиций (многие идентичны), но полезные значения варьируются от 1 до 2070 и заканчивая от 0 до 22 символов после начальной позиции, конечная позиция может быть длиннее, если изменить тип на «P» вместо «L», но повредит производительность.

Эти отдельные строки в каждом ряду подсчитываются. Максимальное количество всегда будет равно количеству строк в табличной переменной '@'. Изменение порядка на том же счетчике приведет к тому, что подстрока с большинством совпадений останется в верхней части результатов, после чего обратная длина подстроки оставит самое длинное совпадение с большинством совпадений сверху. В запросе только выберите 1 верхнюю строку.

Чтобы получить ответы на все вопросы, измените первую часть запроса на

ВЫБЕРИТЕ топ 1 со связями х ОТ

t-clausen.dk
источник
3

C # (интерактивный компилятор Visual C #), 320 257 байт

l=>(string.Join(",",l.Select(s=>new int[s.Length*s.Length*2].Select((i,j)=>string.Concat(s.Skip(j/-~s.Length).Take(j%-~s.Length))))
.Aggregate((a,b)=>a.Intersect(b)).GroupBy(x=>x.Length).OrderBy(x =>x.Key).LastOrDefault()?.Select(y=>y)??new List<string>()));

Попробуйте онлайн!

Реквизит для @Expired Data и @dana

Innat3
источник
Вы можете просто вернуть строку из функции. Так что в Интерактивном компиляторе это может выглядеть примерно так: 294 байта
Истек срок действия данных
1
Вот решение, которое ускорило некоторые байты на 215 байтов
данные
@ExpiredData ах, отлично, это тот пример, который мне нужен :)
Innat3
186
Дана
184
Воплощение Неведения
3

Perl 6 , 62 60 байт

{~sort(-*.comb,keys [∩] .map(*.comb[^*X.. ^*]>>.join))[0]}

Попробуйте онлайн!

Я немного раздражал Perl 6 не может сделать набор операций над списками списков, поэтому есть дополнительный .combи >>там.

Еще одна досадная вещь - это то, что я maxне могу взять функцию для сравнения предметов, то есть sortвместо этого я должен использовать . Как указано в комментариях, max может принимать аргумент, однако он заканчивается дольше, так как мне приходится учитывать maxвозврат отрицательной бесконечности, когда есть общие подстроки ( попробуйте онлайн! ).

Джо Кинг
источник
3
maxможет принимать такую ​​функцию (хотя arity 1) либо по положению при вызове в режиме OO, либо поименованному :byаргументу в процедурном режиме.
Ven
2

Japt v2.0a0 -hF, 8 байт

Îã f@eøX

Спасибо Shaggy за сохранение 3 байта

Попытайся

Îã              //Generate all substrings of the first string
 f@             //Filter; keep the substrings that satisfy the following predicate:
   e            //    If all strings of the input...
    øX          //    Contain this substring, then keep it
-h              //Take last element
-F              //If last element is undefined, default to empty string
Воплощение невежества
источник
Вам не нужно сортировать по длине в конце, экономя 3 байта. Также по -Fумолчанию используется пустая строка.
Мохнатый
2

Japt -h , 8 байт

(Я мог бы сбросить последние 3 байта и использовать -Fhвместо этого флаг, но я не фанат использования -F)

mã rf iP

Попробуйте или запустите все тесты

mã rf iP     :Implicit input of array
m            :Map
 ã           :  Substrings
   r         :Reduce by
    f        :  Filter, keeping only elements that appear in both arrays
      i      :Prepend
       P     :  An empty string
             :Implicit output of last element
мохнатый
источник
1

Python 3 , 137 байт

def a(b):c=[[d[f:e]for e in range(len(d)+1)for f in range(e+1)]for d in b];return max([i for i in c[0]if all(i in j for j in c)],key=len)

Попробуйте онлайн!

Артемида поддерживает Монику
источник
Возможно, вы захотите использовать одиночные пробелы в качестве отступа вместо 4, которые, кажется, бреют более 100 байтов.
Шиеру Асакото
@JoKing tio.run/…
Артемида поддерживает Монику
Итак, вот исправленная версия 135-байтовой программы
Джо Кинг,
1

Python 2 , 103 байта

lambda b:max(reduce(set.__and__,[{d[f:e]for e in range(len(d)+2)for f in range(e)}for d in b]),key=len)

Попробуйте онлайн!

Это анонимная лямбда, которая преобразует каждый элемент во множество всех подстрок, затем reduceустанавливает его через set intersection ( set.__and__), а затем возвращает maxэлемент через length.

Джо Кинг
источник
1 байт короче с set.intersection.
овс
1

Perl 5 ( -aln0777F/\n/ -M5.01 -MList::util=max), 99 байт

может быть в гольф более определенно

map/(.+)(?!.*\1)(?{$h{$&}++})(?!)/,@F;say for grep{y///c==max map y///c,@b}@b=grep@F==$h{$_},keys%h

TIO

Науэль Фуйе
источник
1

Древесный уголь , 30 байт

≔⊟θη≔⁰ζFLη«≔✂ηζ⊕ι¹ε¿⬤θ№κεPε≦⊕ζ

Попробуйте онлайн! Ссылка на подробную версию кода. Этот алгоритм более эффективен и короче, чем генерация всех подстрок. Объяснение:

≔⊟θη

Вставьте последнюю строку из списка ввода в переменную.

≔⁰ζ

Обнулить начальный индекс подстроки.

FLη«

Обведите все возможные индексы конца подстроки. (На самом деле это цикл с 0, исключая длину, поэтому значение корректируется позже.)

≔✂ηζ⊕ι¹ε

Получить текущую подстроку.

¿⬤θ№κε

Проверьте, содержится ли эта подстрока во всех других входных строках.

Pε

Если это так, то замените любую ранее выведенную подстроку

≦⊕ζ

В противном случае попробуйте увеличить начальный индекс подстроки.

Нил
источник
1

Баш , 295 .. 175 байт

Не красиво, но, по крайней мере, это работает. Попробуйте онлайн

-37 путем генеральной уборки ; -52 путем плагиата из zsh ответа ; -26 путем замены массива на цикл ; -2 благодаря GammaFunction ; -3 снято i=0с forпетли

for l;{ d=${#l}
for((;i<d**2;i++)){ a="${l:i/d:1+i%d}" k=
for n;{ [[ $n =~ $a ]]&&((k++));}
((k-$#))||b+=("$a");};}
for e in "${b[@]}";do((${#e}>${#f}))&&f="$e";done
echo "$f"

Вот оригинальный скрипт без комментариев с комментариями

roblogic
источник
1
Сохраните еще 2: Вы можете заменить ((k==$#))&&на ((k-$#))||. Это также позволяет вам использовать k=вместо установки его на 0.
GammaFunction
1
Я думаю, "Не красиво, но, по крайней мере, это работает" - МО для скриптов bash :)
joeytwiddle
0

Красный , 266 174 байта

func[b][l: length? s: b/1 n: 1 until[i: 1 loop n[t: copy/part at s i l r: on foreach u
next b[r: r and(none <> find/case u t)]if r[return t]i: i + 1]n: n + 1 1 > l: l - 1]""]

Попробуйте онлайн!

Изменил рекурсию на итерацию и избавился от сортировки.

Гален Иванов
источник
0

JavaScript (Node.js) , 106 байт

a=>(F=(l,n,w=a[0].substr(n,l))=>l?n<0?F(--l,L-l):a.some(y=>y.indexOf(w)<0)?F(l,n-1):w:"")(L=a[0].length,0)

Попробуйте онлайн!

a=>(                      // Main function
 F=(                      //  Helper function to run through all substrings in a[0]
  l,                      //   Length
  n,                      //   Start position
  w=a[0].substr(n,l)      //   The substring
 )=>
 l?                       //   If l > 0:
  n<0?                    //    If n < 0:
   F(--l,L-l)             //     Check another length
  :a.some(                //    If n >= 0: 
   y=>y.indexOf(w)<0      //     Check whether there is any string not containing the substring
                          //     (indexOf used because of presence of regex special characters)
  )?                      //     If so:
   F(l,n-1)               //      Check another substring
  :w                      //     If not, return this substring and terminate
                          //     (This function checks from the longest substring possible, so
                          //      it is safe to return right here)
 :""                      //   If l <= 0: Return empty string (no common substring)
)(
 L=a[0].length,           //  Starts from length = the whole length of a[0]
 0                        //  And start position = 0
)
Сиеру Асакото
источник
0

Gaia , 15 байт

eḋ¦&⊢⟨:l¦:⌉=¦⟩∇

Попробуйте онлайн!

e		| eval as code
 ḋ¦		| find all non-empty substrings
   &⊢		| Reduce by set intersection
              ∇	| and return the first element where
      ⟨:l¦:⌉=¦⟩	| the length is equal to the max length
Giuseppe
источник
0

PowerShell , 165 163 87 байт

-76 байт благодаря Nail для удивительного регулярного выражения .

"$($args-join'
'|sls "(?<=^.*)(.+)(?=(.*\n.*\1)*.*$)"-a -ca|% m*|sort Le*|select -l 1)"

Попробуйте онлайн!

Менее гольф:

$multilineArgs = $args-join"`n"
$matches = $multilineArgs|sls "(?<=^.*)(.+)(?=(.*\n.*\1)*.*$)" -AllMatches -CaseSensitive|% matches
$longestOrNull = $matches|sort Length|select -Last 1
"$longestOrNull"
Mazzy
источник
0

Java (JDK) , 158 байт

a->{for(int l=a.get(0).length(),i=l,j;i>=0;i--)for(j=0;j<l-i;){var s=a.get(0).substring(j++,j+i);if(a.stream().allMatch(x->x.contains(s)))return s;}return"";}

Попробуйте онлайн!

кредиты

Оливье Грегуар
источник
1
159 байт (удалены контрольные примеры, чтобы поместить ссылку TIO в комментарий)
Сара Дж
0

Pyth , 16 байт

eolN.U@bZm{s./dQ

Попробуйте онлайн!

       m     Q    # Map Q (parsed input) over the following function (lambda d:
          ./d     # Partitions of d (all substrings)
         s        # Reduce on + (make one list)
        {         # deduplicate
    .U            # reduce the result on the following lambda, with starting value result[0]
      @bZ         # lambda b,Z: Intersection between b and Z
                  # Result so far: all common substrings in random order
 o                # sort the resulting sets by the following lambda function:
  lN              # lambda N: len(N)
e                 # last element of that list
ar4093
источник