Utwórz program lub funkcję, która pobiera listę ciągów jako dane wejściowe i wyświetla najdłuższy ciąg, który jest podciągiem wszystkich ciągów wejściowych. Jeśli istnieje kilka podciągów o równej długości i już nie jest podciągających, wypisz jeden z nich.

• Może to oznaczać wyprowadzenie pustego ciągu.
• Jeśli istnieje kilka prawidłowych wyników, możesz wypisać dowolne z nich. Nie musisz podawać spójnych danych wyjściowych dla danych wejściowych, o ile dane wyjściowe są zawsze prawidłowe.
• Na wejściu zawsze będzie co najmniej jeden ciąg, ale może nie być niepustego ciągu.
• Wszystkie drukowane znaki ASCII mogą pojawić się na wejściu. Możesz założyć, że są to jedyne pojawiające się postacie.
• Możesz pobierać dane wejściowe lub generować dane wyjściowe dowolną z metod domyślnych .
• Standardowe luki są niedozwolone.
• To jest golf golfowy - im mniej bajtów kodu, tym lepiej.

Przypadki testowe:

[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 bajty

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)

Wypróbuj online!

Pobiera dane wejściowe. Przekroczy limit czasu dla danych wejściowych, w których pierwszy ciąg jest długi.

Chodzi o to, aby wziąć podciągi pierwszych ciągów, haby znaleźć najdłuższy, który pojawia się we wszystkich pozostałych ciągach t. Aby to zrobić, rekurencyjnie rozgałęziamy się po usunięciu pierwszego lub ostatniego znaku h.

Python 2 , 94 bajty

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

Wypróbuj online!

Bardziej bezpośrednia metoda. Funkcja pomocnicza ggeneruje zestaw wszystkich podciągów s, a funkcja główna zajmuje najdłuższą na swoim skrzyżowaniu.

Brachylog (v2), 3 9 bajtów

{sᵛ}ᶠlᵒtw

Wypróbuj online!

Pełny program Wejście ze standardowego wejścia (jako lista ciągów w stylu JSON), wyjście na standardowe wyjście.

Wyjaśnienie

{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

Najwyraźniej kolejność rozstrzygania remisów snie jest taka, jak w prawie wszystkich innych elementach Brachylog, więc musimy ręcznie ją zastąpić, aby uzyskać jak najdłuższy wynik. (To trochę frustrujące: cztery dodatkowe znaki do zastąpienia oraz dwa znaki grupujące, ponieważ Brachylog nie analizuje dwóch metapredykatów z rzędu).

Brachylog snie zwraca pustych podciągów, więc potrzebujemy trochę sztuczki, aby sobie z tym poradzić: zamiast składać funkcję (co jest normalnie wykonywane), piszemy pełny program, wypisujący na standardowe wyjście. W ten sposób, jeśli istnieje wspólny substring, po prostu go wyprowadzamy i gotowe. Jeśli nie ma wspólnego podłańcucha, program wyskakuje - ale nadal nie wypisuje nic na standardowe wyjście, więc wypisuje ciąg zerowy zgodnie z przeznaczeniem.

Galaretka , 12 6 bajtów

Ẇ€f/ṫ0

Wypróbuj online!

Dzięki @JonathanAllan za uratowanie 6 bajtów!

Ruby 2.6, 76 59 54 bajtów

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

Wypróbuj online! - Wersja Ruby 2.5 (56 bajtów)

W jaki sposób?

Utwórz listę potencjalnych dopasowań, początkowo ustawioną na oryginalną tablicę. Iteruj na liście, a jeśli ciąg nie pasuje, dodaj 2 nowe ciągi do końca listy, odcinając pierwszy lub ostatni znak. Na końcu zostanie znalezione dopasowanie (ewentualnie pusty ciąg).

Dzięki Kirill L za -2 bajty i histokrat za kolejne -2

R , 119 116 108 106 bajtów

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

Wypróbuj online!

Znajdź wszystkie podłańcuchy każdego łańcucha, znajdź przecięcie każdej listy podciągów, a następnie w końcu zwróć (jeden z) najdłuższych.

-3 bajty dzięki Kirill L.

-8 bajtów lapply zamiast Map

-2 bajty dzięki Kirillowi L. ponownie, usuwając aparat ortodontyczny

05AB1E , 14 9 8 bajtów

€Œ.«ÃéθJ

-6 bajtów dzięki @Adnan .

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

€Œ       # 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 bajtów

-3 bajtów z arytmetyki dla, -6 bajtów z niejawnych "$@"(dzięki roblogic), -5 bajtów z usuwania niepotrzebnych { }, -1 bajtów z krótkiej formy for, -1 bajtów przy użyciu repeat, -1 bajtów przez konkatenację for s ($b)z ciałem, -13 bajtów zmieniając pętlę powtarzania dla jakiegoś ewankowego kija.

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

Wypróbuj online! Wypróbuj online! Wypróbuj online!

Wczytujemy wszystkie możliwe podciągi do tablicy a, a następnie ustawiamy bna przecięcie tablic ai b. Konstrukt ${b-$a}podmieni się tylko $aprzy pierwszej iteracji: W przeciwieństwie do rozszerzenia rodzeństwa ${b:-$a}, nie zastąpi, gdy bjest ustawiony, ale pusty.

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 bajtów

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

Wypróbuj online!

Zbierz wszystkie sufiksy ( tails) pierwszego słowa xna liście i podejmują wszystkie prefiksy ( inits) tych przyrostków, aby uzyskać wszystkie podciągi so x. Sobie nawzajem s, że isInfixOf allstruny na liście pozostały r. Uporządkować te podciągi pod względem długości (korzystając z (0<$)podstęp ) i powrócić ostatni.

Retina 0.8.2 , 48 bajtów

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

Wypróbuj online! Wyjaśnienie:

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

Dla każdego sufiksu pierwszego łańcucha znajdź najdłuższy prefiks, który jest jednocześnie podciągiem wszystkich pozostałych łańcuchów. Wymień wszystkie prefiksy sufiksów (tzn. Podłańcuchy). Jeśli nie ma pasujących podciągów, po prostu kończymy na pustym ciągu, czego i tak chcemy.

O#$^`
$.&

Posortuj podciągi w odwrotnej kolejności według długości.

1G`

Zachowaj tylko pierwszy, czyli najdłuższy podciąg.

Zapytanie TSQL, 154 bajty

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)

Wypróbuj online

Uwzględniono wielkość liter, deklarując kolumnę „a” z zestawieniem zawierającym CS (wielkość liter ma znaczenie).

Rozdzielając wszystkie ciągi znaków z 2540 pozycji początkowych (wiele identycznych), ale przydatne wartości mieszczą się w zakresie od 1 do 2070 i kończąc od 0 do 22 znaków po pozycji początkowej, pozycja końcowa może być dłuższa przez zmianę typu na „P” zamiast „L”, ale osłabiłoby wydajność.

Te odrębne ciągi znaków w każdym numerze są liczone. Najwyższa liczba będzie zawsze równa liczbie wierszy w zmiennej tabeli „@”. Odwrócenie kolejności o tę samą liczbę spowoduje pozostawienie podciągu z większością dopasowań na górze wyników, a następnie odwrócona długość podłańcucha pozostawi najdłuższe dopasowanie z większością dopasowań na górze. Zapytanie wybiera tylko pierwszy wiersz.

Aby uzyskać wszystkie odpowiedzi, zmień pierwszą część zapytania na

WYBIERZ top 1 z krawatami x OD

C # (interaktywny kompilator Visual C #), 320 257 bajtów

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

Wypróbuj online!

Rekwizyty do @Expired Data i @dana

Perl 6 , 62 60 bajtów

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

Wypróbuj online!

Jestem trochę zirytowany Perl 6 nie może zrobić zestaw operacji na listach list, dlatego istnieje dodatkowy .combi >>tam.

Inną irytującą rzeczą jest to, że maxnie może wziąć funkcji porównywania przedmiotów, co oznacza, że ​​muszę użyć sortzamiast tego. Jak wskazano w komentarzach, max można wziąć argument, jednak kończy się to dłużej, ponieważ muszę wziąć pod uwagę maxzwracanie ujemnej nieskończoności, gdy występują wspólne podciągi ( Wypróbuj online! ).

Japt v2.0a0 -hF, 8 bajtów

Îã f@eøX

Dzięki Shaggy za uratowanie 3 bajtów

Spróbuj

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

Japt -h , 8 bajtów

(Mógłbym zrzucić ostatnie 3 bajty i -Fhzamiast tego użyć flagi, ale nie jestem fanem używania -F)

mã rf iP

Wypróbuj lub uruchom wszystkie przypadki testowe

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 bajtów

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)

Wypróbuj online!

Python 2 , 103 bajty

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)

Wypróbuj online!

Jest to anonimowa lambda, która przekształca każdy element w zestaw wszystkich podciągów, następnie reduces to przez set przecięcie ( set.__and__), a następnie zwraca maxelement przez length.

C # (interaktywny kompilator Visual C #) , 147 145 bajtów

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

Wypróbuj online!

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

może być golfem z pewnością

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 bajtów

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

Wypróbuj online!

Węgiel drzewny , 30 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Algorytm ten jest bardziej wydajny i krótszy niż generowanie wszystkich podciągów. Wyjaśnienie:

≔⊟θη

Pop ostatni ciąg z listy wprowadzania do zmiennej.

≔⁰ζ

Zeruj indeks początkowy podłańcucha.

ＦＬη«

Pętla nad wszystkimi możliwymi wskaźnikami końca podłańcucha. (Właściwie to pętle od 0 wyłączają długość, więc wartość jest korygowana później.)

≔✂ηζ⊕ι¹ε

Uzyskaj bieżący podciąg.

¿⬤θ№κε

Sprawdź, czy ten podciąg jest zawarty we wszystkich innych ciągach wejściowych.

Ｐε

Jeśli tak, to nadrukuj poprzednio wyprowadzony podciąg.

≦⊕ζ

W przeciwnym razie spróbuj zwiększyć indeks początkowy podłańcucha.

Bash , 295 .. 175 bajtów

Nie ładna, ale przynajmniej działa. Wypróbuj online

-37 przez ogólne sprzątanie ; -52 poprzez plagiat z odpowiedzi zsh ; -26 poprzez zamianę tablicy na pętlę ; -2 dzięki GammaFunction ; -3 usunięto i=0z forpętli

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"

Oto oryginalny niepolecany skrypt z komentarzami

Czerwony , 266 174 bajtów

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

Wypróbuj online!

Zmieniłem rekurencję na iterację i pozbyłem się sortowania.

Perl 5 , 87 bajtów

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

Wypróbuj online!

JavaScript (Node.js) , 106 bajtów

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)

Wypróbuj 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 bajtów

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

Wypróbuj 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 bajtów

-76 bajtów dzięki Nail za niesamowite wyrażenie regularne .

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

Wypróbuj online!

Mniej golfa:

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

JavaScript (Node.js) , 90 bajtów

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

Wypróbuj online! Przypadki testowe bezwstydnie skradzione z @Arnauld. Port mojej odpowiedzi na węgiel drzewny.

Java (JDK) , 158 bajtów

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

Wypróbuj online!

Kredyty

• -17 bajty dzięki Sara J .

Perl 5 , 86 bajtów

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

Wypróbuj online!

Pyth , 16 bajtów

eolN.U@bZm{s./dQ

Wypróbuj 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