Powtarzaj za mną!

23

Biorąc pod uwagę ciąg jako argument, wypisz długość najdłuższego (-ych) powtarzającego się podciągu (ciągów) lub zero, jeśli nie ma takiego ciągu.

Możesz założyć, że łańcuch wejściowy nie jest pusty.

Przykłady

abcdefabc: podciąg abcjest powtarzany w pozycjach 1 i 7, więc program powinien wypisać 3

abcabcabcabcab: abcabclub bcabcalub cabcabsą powtarzane, więc program powinien wypisać 6 . (podciąg abcabcabcabrównież się powtarza, ale wystąpienia nakładają się, więc go nie akceptujemy).

aaaaaaa: aaapowtarza się na przykład w pozycjach 1 i 4, więc program powinien wypisać 3

abcda: apowtarza się, więc program powinien wypisać 1

xyz: brak powtarzającego się ciągu → 0

ababcabcabcabcab: powinien zwrócić 6

To jest , więc wygrywa najmniej bajtów.

Arnaud
źródło
1
Czy ciąg może być pusty? Jeśli tak jest, czy byłoby dozwolone wyprowadzenie False zamiast 0 ?
Dennis,
@ Dennis Możesz założyć, że łańcuch nie jest pusty.
Arnaud,

Odpowiedzi:

9

pieprzenie mózgu, 226 bajtów

,[<<<,]+[>>->[[[[>>[>>>]<+<-<[<<<]>>+<-]>[<+>-]>[>>>]<<[>[<+>-]]>[[<+>-]>+[<<<]>
>>-[+>[<<<]<[>+>[->]<<[<]>-]>[<+>>+<-]>>>[>>>]]>>]<]>+[,<<<+]->[<<<]>>>>>+[,+>>>
+]-[>>>]->]<[+<<<]+<<<++[->>>]+>>>->]<[,<<<]<[>>>+<<<-]>+>,>>>]<<.

Sformatowany:

,[<<<,]
+
[
  for each suffix
  >>->
  [
    for each prefix
    [
      for each suffix
      [
        for each char while no mismatch
        [
          >>[>>>]
          <+<-<[<<<]
          > >+<-
        ]
        >[<+>-]
        >[>>>]
        <<
        [
          mismatch
          >[<+>-]
        ]
        >
        [
          [<+>-]
          >+[<<<]
          >>>-
          [
            match
            +>[<<<]
            <
            [
              >+>[->]
              <<[<]
              >-
            ]
            >[<+> >+<-]
            >>>[>>>]
          ]
          >>
        ]
        <
      ]
      >+[,<<<+]
      ->[<<<]
      >>> >>+[,+>>>+]
      -[>>>]
      ->
    ]
    <[+<<<]
    +<<<++[->>>]
    +>>>->
  ]
  <[,<<<]
  <[>>>+<<<-]
  >+>,>>>
]
<<.

Oczekuje danych wejściowych z końcowym znakiem nowej linii lub bez i wyświetla wynik jako wartość bajtu .

Wypróbuj online.

Sprawdza każdy prefiks, aby sprawdzić, czy występuje on później w ciągu, a następnie odcina pierwszy znak i powtarza proces, aż nie pozostanie więcej znaków.

Taśma jest podzielona na 3-komórkowe węzły,

c 0 f

gdzie cjest znakiem danego ciągu i fjest flagą, która może być jedna, ujemna lub zero. Flagi niezerowe są umieszczane między dwoma obecnie porównywanymi znakami, a ujemne są zarezerwowane dla komórek po zakończeniu bieżącego prefiksu i przed początkiem bieżącego sufiksu (tj. Przed indeksem bieżącego potencjalnego dopasowania).

Wynik jest przechowywany po lewej stronie ciągu i jest aktualizowany za każdym razem, gdy zostanie znalezione dopasowanie.

(Ciąg jest faktycznie przetwarzany w odwrotnej kolejności z \x01dołączonym do niego).

Mitch Schwartz
źródło
6

Galaretka , 12 bajtów

œ-QL€
ŒṖÇ€FṀ

Wypróbuj online!

Jak to działa

ŒṖÇ€FṀ  Main link. Argument: s (string)

ŒṖ      Generate all partitions of s.
  ǀ    Apply the helper link to each partition.
    F   Flatten the resulting array of lengths.
     Ṁ  Take the maximum.


œ-QL€   Helper link. Argument: P (partition)

  Q     Yield the elements of P, deduplicated.
œ-      Multiset subtraction; remove exactly one occurrence of each string in P.
   L€   Compute the lengths of the remaining strings. 
Dennis
źródło
1
Niech żyje Jelly, najlepszy kod golfowy!
Nissa,
œ-Qjest naprawdę fajnie.
Lynn,
5

Perl 6 , 36 bajtów

{m:ex/(.*).*$0/.map(*[0].chars).max}

Spróbuj

Rozszerzony:

{   # bare block lambda with implicit parameter 「$_」

  m           # match ( implicitly against 「$_」
  :exhaustive # every possible way
  /
    (.*)      # any number of characters ( stored in 「$0」 )
    .*
    $0
  /

  .map(

    *\        # the parameter to Whatever lambda
    [0]\      # the value that was in 「$0」 for that match
    .chars    # the number of characters

  ).max

}
Brad Gilbert b2gills
źródło
5

Siatkówka , 35 32 30 bajtów

Całkiem fajne wyzwanie.

M&!`(.*)(?=.*\1)
M%`.
O#^`
G1`

Wypróbuj online

Wyjaśnienie:

M&!`(.*)(?=.*\1)    # Prints overlapping greedy substrings occuring more than once
M%`.                # Replace each line with its length
O#^`                # Sort lines by number in reverse
G1`                 # Return the first line
mbomb007
źródło
Możesz zapisać dwa bajty, używając M%`.jako drugiego etapu.
Martin Ender
4

JavaScript (ES6), 79 68 66 bajtów

f=(s,r,l=s.match(/(.*).*\1/)[1].length)=>s?f(s.slice(1),l<r?r:l):r
<input oninput=o.textContent=f(this.value)><pre id=o>

Edycja: Zapisano 11 13 bajtów dzięki @Arnauld.

Neil
źródło
4

Haskell , 79 bajtów

(""%)
(a:b)!(c:d)|a==c=1+b!d
_!_=0
a%c@(e:d)=maximum[a!c,""%d,(a++[e])%d]
_%_=0

Wypróbuj online!

Kreator pszenicy
źródło
2
Wygląda na to, że pierwszy argument %może kumulować aaaxayaa
niesąsiadującą
Co powiedział @xnor. Myślę, że rekurencyjne wezwanie do a%djest złe, ale także niepotrzebne. Co oznacza również, że możesz użyć maxzamiast maximum.
Ørjan Johansen
1
Myślę, że zmiana a%dto ""%dnaprawia.
xnor
No tak, nadal jest potrzebny (i dźwięk), kiedy ajest pusty.
Ørjan Johansen
1
Myślę, że sum[1|(x,y)<-zip a c,x==y]można go użyć zamiast a!c.
Laikoni
2

JavaScript, 120

function r(a,b,m){return b=-~b,t=a.slice(0,b),n=a.indexOf(t,b),m=b>m&&!~n?m:b,a!=t&&r(a,b,m)||(a?r(a.slice(1),m,m):~-m)}
C5H8NNaO4
źródło
2

Łuska , 11 bajtów

L►L§fo↓2`xQ

Wypróbuj online!

Uwaga: Łuska jest nowsza niż to wyzwanie.

Wyjaśnienie

L►L§fo↓2`xQ  Implicit input, say x = "ababc"
          Q  Nonempty substrings: ["a","b","ab",..,"ababc"]
    f        Keep those that satisfy this:
              Take s = "ab" as an example.
   §    `x    Split x along s: ["","","c"]
     o↓2      Drop the first two pieces: ["c"]
              This is truthy (i.e. nonempty).
             Result is ["a","b","ab","a","b","ab"]
 ►L          Take element with maximal length: "ab"
             If the list is empty, "" is used instead.
L            Length: 2
Zgarb
źródło
2

Perl 5 z -p, 40 bajtów

$_+=(sort map{y///c}/(?=(.+).*\1)/g)[-1]

Wypróbuj online!

Dom Hastings
źródło
1

Mathematica, 75 65 bajtów

10 bajtów zapisanych dzięki @JingHwan Min .

Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]&

Funkcja anonimowa. Pobiera ciąg znaków jako dane wejściowe i zwraca liczbę jako dane wyjściowe.

LegionMammal978
źródło
Nie sądzę, żebyś potrzebował początku i końca, BlankNullSequence (___)kiedy Overlaps->Alltam będzie. Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]&byłoby dobrze.
JungHwan Min.
@JungHwanMin Dzięki, myliłem to z StringReplace: P
LegionMammal978
1

Pyth - 16 bajtów

Muszę w golfa przekonwertować wszystkie struny na długości i znaleźć maks.

eSlM+ksmft/dTd./

Pakiet testowy .

Maltysen
źródło
1

Clojure, 112 bajtów

#(apply max(for[R[(range(count %))]j R i R](let[[b e](split-at i(drop j %))](if((set(partition i 1 e))b)i 0)))))

Pętle dwa razy w ciągu liczb 0do n - 1( njest długość łańcucha), krople jznaki i dzieli pozostałą do „początku” i części „END”. Tworzy zestaw wszystkich podciągów edługości bi używa go jako funkcji do sprawdzenia, czy bstamtąd zostanie znaleziony. Zwraca długość, bjeśli znaleziono, a 0 w przeciwnym razie zwraca maksimum tych wartości.

Byłoby ciekawie zobaczyć krótszą wersję.

NikoNyrh
źródło
1

Siatkówka , 24 bajty

L$v`(.*).*\1
$.1
N`
G-1`

Wypróbuj online!

Rozgrzewka dla mnie, aby nauczyć się nowych funkcji Retina 1.

Wyjaśnienie

L$v`(.*).*\1
$.1

Etap listy zwraca wszystkie dopasowania wyrażenia regularnego (.*).*\1, które pasują do dowolnego wzorca postaci „ABA”, gdzie A i B są dwoma dowolnymi podciągami (być może pustymi). Dodatkowe opcje podane dla tego etapu to: vuwzględnianie nakładających się meczów, $które stosują podstawienie do każdego dopasowania przed jego zwróceniem: podstawienie jest wskazane w drugim wierszu i odpowiada długości ( .) pierwszej grupy przechwytywania ( który byłby podciągiem „A” w poprzednim przykładzie).

N`

Mamy teraz wszystkie długości powtarzających się podciągów, ten etap po prostu sortuje je w kolejności numerycznej, od najkrótszego do najdłuższego.

G-1`

Wreszcie, ten etap grep ( G) zachowuje tylko ostatni -1wynik ( ), który jest długością najdłuższego powtarzanego podłańcucha.

Lew
źródło
0

JavaScript, 165 bajtów

function a(s){var l=s.length/2,z=1,f='';while(z<=l){var t=s.substr(0,z),c=0;for(var i=0;i<s.length;i++){if(s.substr(i,z)===t){c++;if(c>1){f=t}}}z++}return f.length}

Przypadki testowe

console.log(a('abcabcabcabc')) // Output 6
console.log(a('xyz'))          // Output 0
console.log(a('aaaaaaa'));     // Output 3
console.log(a('abcdefabc'));   // Output 3
Lalith Prasad
źródło
2
Witamy w Programowaniu Puzzle i Code Golf. Niestety zwraca 2 dla danych wejściowych ababcabcabcabcab, ale ciąg cabcabjest powtarzany.
Dennis