Crie um programa ou função que tome uma lista de cadeias como entrada e produza a cadeia mais longa que é uma substring de todas as cadeias de entrada. Se houver várias substrings de comprimento igual e não mais substring, produza qualquer uma delas.

• Isso pode significar a saída da string vazia.
• Se houver várias saídas válidas, você poderá produzir qualquer uma delas. Você não precisa fornecer uma saída consistente para uma determinada entrada, desde que a saída seja sempre válida.
• Sempre haverá pelo menos uma sequência na entrada, mas pode não haver uma sequência não vazia.
• Todos os caracteres ASCII imprimíveis podem aparecer na entrada. Você pode assumir que esses são os únicos caracteres que aparecem.
• Você pode receber entrada ou produzir saída por qualquer um dos métodos padrão .
• As brechas padrão não são permitidas.
• Isso é código-golfe - quanto menos bytes de código, melhor.

Casos de teste:

[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"] -> ["&"]

Python 2 , 82 bytes

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)

Experimente online!

Pega entrada splatted. Tempo limite para entradas onde a primeira string é longa.

A idéia é pegar substrings das primeiras strings hpara encontrar a mais longa que aparece em todas as strings restantes t. Para fazer isso, ramificamos recursivamente a remoção do primeiro ou do último caractere de h.

Python 2 , 94 bytes

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

Experimente online!

Um método mais direto. A função auxiliar ggera o conjunto de todas as subseqüências se a função principal leva a mais longa em sua interseção.

Brachylog (v2), 3 9 bytes

{sᵛ}ᶠlᵒtw

Experimente online!

Programa completo. Entrada da entrada padrão (como uma lista de strings no estilo JSON), saída para saída padrão.

Explicação

{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

Aparentemente, a ordem de desempate snão é a que está em quase todo o resto no Brachylog, portanto, precisamos substituí-lo manualmente para produzir a saída mais longa. (Isso é um pouco frustrante: quatro caracteres extras para a substituição, mais dois caracteres de agrupamento porque o Brachylog não analisa dois metapredicados seguidos.)

O Brachylog's snão retorna substrings vazios, então precisamos de um truque para contornar isso: em vez de enviar uma função (o que normalmente é feito), escrevemos um programa completo, com saída para a saída padrão. Dessa forma, se houver uma substring comum, apenas a produzimos e terminamos. Se não houver uma substring comum, o programa errará - mas ele ainda não imprime nada na saída padrão; portanto, gera a string nula conforme pretendido.

Gelatina , 12 6 bytes

Ẇ€f/ṫ0

Experimente online!

Obrigado a @ JonathanAllan por salvar 6 bytes!

Ruby 2.6, 76 59 54 bytes

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

Experimente online! - Versão Ruby 2.5 (56 bytes)

Quão?

Crie uma lista de possíveis correspondências, inicialmente configuradas para a matriz original. Itere na lista e, se uma string não corresponder, adicione 2 novas strings ao final da lista, cortando o primeiro ou o último caractere. No final, uma correspondência (eventualmente uma string vazia) será encontrada.

Obrigado Kirill L por -2 bytes e histocrata por mais -2

R , 119 116 108 106 bytes

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

Experimente online!

Encontre todas as substrings de cada string, encontre a interseção de cada lista de substrings e, finalmente, retorne (uma de) a mais longa.

-3 bytes graças a Kirill L.

-8 bytes usando em lapply vez de Map

-2 bytes graças a Kirill L. novamente, removendo chaves

05AB1E , 14 9 8 bytes

€Œ.«ÃéθJ

-6 bytes graças a @Adnan .

Experimente online ou verifique todos os casos de teste .

Explicação:

€Œ       # 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)

Zsh , 126 ... 96 bytes

-3 bytes de aritmética para, -6 bytes de implícito "$@"(obrigado roblogic), -5 bytes de remoção desnecessária { }, -1 byte de forma abreviada de for, -1 byte usando repeat, -1 byte usando , -1 byte concatenando for s ($b)com seu corpo, -13 bytes alterando o loop de repetição para algum jaleco de avaliação.

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

Experimente online! Experimente online! Experimente online!

Lemos todas as substrings possíveis na matriz ae, em seguida, definimos ba interseção das matrizes ae b. A construção ${b-$a}substituirá apenas $ana primeira iteração: Ao contrário da expansão entre irmãos ${b:-$a}, ela não substituirá quando bestiver configurada, mas vazia.

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

Haskell , 80 bytes

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

Experimente online!

Obtenha todos os sufixos ( tails) da primeira palavra xna lista e use todos os prefixos ( inits) desses sufixos para obter todas as substrings sde x. Mantenha cada um sque isInfixOf allcordas na lista restante r. Classifique essas substrings por comprimento (usando o (0<$)truque ) e retorne a última.

Retina 0.8.2 , 48 bytes

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

Experimente online! Explicação:

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

Para cada sufixo da primeira sequência, encontre o prefixo mais longo que também é uma substring de todas as outras sequências. Liste todos esses prefixos de sufixo (ou seja, substrings). Se não houver substrings correspondentes, acabamos com a string vazia, que é o que queremos de qualquer maneira.

O#$^`
$.&

Classifique as substrings na ordem inversa do comprimento.

1G`

Mantenha apenas o primeiro, ou seja, o substring mais longo.

Consulta TSQL, 154 bytes

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)

Experimente online

Tornou diferenciação de maiúsculas e minúsculas declarando a coluna 'a' com agrupamento contendo CS (diferencia maiúsculas de minúsculas).

Dividindo todas as cadeias de caracteres de 2540 posições iniciais (muitas idênticas), mas os valores úteis variam entre 1 e 2070 e terminando de 0 a 22 caracteres após a posição inicial, a posição final pode ser mais longa alterando o tipo para 'P' em vez de 'L', mas prejudicaria o desempenho.

Essas seqüências distintas em cada número de rown são contadas. A contagem mais alta sempre será igual ao número de linhas na variável da tabela '@'. A reversão da ordem na mesma contagem deixará a substring com a maioria das correspondências por cima dos resultados, seguida pelo comprimento invertido da substring deixará a correspondência mais longa com a maioria das correspondências por cima. A consulta seleciona apenas a primeira linha 1.

Para obter todas as respostas, altere a primeira parte da consulta para

SELECIONE os 1 primeiros com laços x FROM

C # (compilador interativo do Visual C #), 320 257 bytes

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

Experimente online!

Adereços para @Expired Data e @dana

Perl 6 , 62 60 bytes

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

Experimente online!

Estou um pouco chateado porque o Perl 6 não pode fazer operações definidas em listas de listas, e é por isso que há um extra .combe >>lá dentro.

Outra coisa irritante é que maxnão é possível usar uma função para comparar itens, o que significa que eu tenho que usar sort. Como apontado nos comentários, max pode-se usar um argumento, no entanto, acaba sendo mais demorado, pois tenho que levar em conta o maxretorno do infinito negativo quando existem substrings comuns ( tente online! ).

Japt v2.0a0 -hF, 8 bytes

Îã f@eøX

Obrigado a Shaggy por salvar 3 bytes

Tente

Îã              //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

Japonês -h , 8 bytes

(Eu poderia derrubar os últimos 3 bytes e usar a -Fhsinalização, mas não sou fã disso -F)

mã rf iP

Experimente ou execute todos os casos de teste

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

Python 3 , 137 bytes

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)

Experimente online!

Python 2 , 103 bytes

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)

Experimente online!

Este é um lambda anônimo que transforma cada elemento no conjunto de todas as subseqüências, depois reduceo define intersection ( set.__and__) e, em seguida, retorna o maxelemento por leng.

C # (compilador interativo do Visual C #) , 147 145 bytes

a=>{int i=0,j,m=0,k=a[0].Length;string s="",d=s;for(;i<k;i++)for(j=m;j++<k-i;)if(a.All(y=>y.Contains(s=a[0].Substring(i,j)))){m=j;d=s;}return d;}

Experimente online!

Perl 5 ( -aln0777F/\n/ -M5.01 -MList::util=max), 99 bytes

pode ser jogado com mais certeza

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

TIO

JavaScript (ES6),  98  92 bytes

a=>(g=b=s=>a.every(x=>~x.indexOf(s))?b=b[s.length]?b:s:g(s.slice(0,-1,g(s.slice(1)))))(a[0])

Experimente online!

Carvão , 30 bytes

≔⊟θη≔⁰ζＦＬη«≔✂ηζ⊕ι¹ε¿⬤θ№κεＰε≦⊕ζ

Experimente online! Link é a versão detalhada do código. Esse algoritmo é mais eficiente e mais curto do que gerar todas as substrings. Explicação:

≔⊟θη

Coloque a última string da lista de entrada em uma variável.

≔⁰ζ

Zere o índice inicial da substring.

ＦＬη«

Faça um loop sobre todos os possíveis índices finais de substring. (Na verdade, isso passa de 0 excluindo o comprimento, portanto o valor é ajustado posteriormente.)

≔✂ηζ⊕ι¹ε

Obtenha a substring atual.

¿⬤θ№κε

Verifique se esta substring está contida em todas as outras seqüências de entrada.

Ｐε

Se for, imprimir sobre qualquer substring de saída anterior.

≦⊕ζ

Caso contrário, tente incrementar o índice inicial da substring.

Bash , 295 .. 175 bytes

Não é bonito, mas pelo menos funciona. Experimente Online

-37 por limpeza geral ; -52 plagiando com a resposta zsh ; -26 substituindo array por um loop ; -2 graças a GammaFunction ; -3 removido i=0do forloop

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"

Aqui está o script original não destruído, com comentários

Vermelho , 266 174 bytes

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]""]

Experimente online!

Mudou a recursão para a iteração e se livrou da classificação.

Perl 5 , 87 bytes

my$r;"$&@_"=~/(.{@{[$r=~y,,,c]},}).*(\n.*\1.*){@{[@_-1]}}/ and$r=$1while$_[0]=~s,.,,;$r

Experimente online!

JavaScript (Node.js) , 106 bytes

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)

Experimente online!

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
)

Gaia , 15 bytes

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

Experimente online!

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

PowerShell , 165 163 87 bytes

-76 bytes graças a Nail para o incrível regexp .

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

Experimente online!

Menos golfe:

$multilineArgs = $args-join"`n"
$matches = $multilineArgs|sls "(?<=^.*)(.+)(?=(.*\n.*\1)*.*$)" -AllMatches -CaseSensitive|% matches
$longestOrNull = $matches|sort Length|select -Last 1
"$longestOrNull"

JavaScript (Node.js) , 90 bytes

f=(a,s=e=0,w='')=>a[0][e]?f(a,s+(r=a.some(x=>!x.includes(t),t=a[0].slice(s,++e))),r?w:t):w

Experimente online! Casos de teste roubados descaradamente do @Arnauld. Porto da minha resposta de carvão.

Java (JDK) , 158 bytes

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"";}

Experimente online!

Créditos

• -17 bytes graças a Sara J .

Perl 5 , 86 bytes

$_=join"\x1",<>;$p=".*\x1.*\\1"x($.-1);say+(sort{length$b-length$a}/(.+)(?=$p)/msg)[0]

Experimente online!

Pitão , 16 bytes

eolN.U@bZm{s./dQ

Experimente online!

       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