Sprich mir nach!

23

Wenn Sie eine Zeichenfolge als Argument angeben, geben Sie die Länge der längsten nicht überlappenden wiederholten Teilzeichenfolge (n) oder Null aus, wenn keine solche Zeichenfolge vorhanden ist.

Sie können davon ausgehen, dass die Eingabezeichenfolge nicht leer ist.

Beispiele

abcdefabc: Der Teilstring abcwird an den Positionen 1 und 7 wiederholt, daher sollte das Programm 3 ausgeben

abcabcabcabcab: abcabcoder bcabcaoder cabcabwerden wiederholt, daher sollte das Programm 6 ausgeben . (Die Teilzeichenfolge abcabcabcabwird ebenfalls wiederholt, die Vorkommen überlappen sich jedoch, sodass wir sie nicht akzeptieren.)

aaaaaaa: aaawird beispielsweise an den Positionen 1 und 4 wiederholt, daher sollte das Programm 3 ausgeben

abcda: awird wiederholt, daher sollte das Programm 1 ausgeben

xyz: keine wiederholte Zeichenfolge → 0

ababcabcabcabcab: sollte zurückkehren 6

Das ist , also gewinnen die wenigsten Bytes.

Arnaud
quelle
1
Könnte die Zeichenfolge leer sein? Wenn dies der Fall ist, darf False anstelle von 0 ausgegeben werden ?
Dennis
@ Tennis Sie können davon ausgehen, dass die Zeichenfolge nicht leer ist.
Arnaud

Antworten:

9

Brainfuck, 226 Bytes

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

Formatiert:

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

Erwartet eine Eingabe mit oder ohne nachfolgende Newline und gibt das Ergebnis als Byte-Wert aus .

Probieren Sie es online aus.

Dadurch wird für jedes Präfix geprüft, ob es später in der Zeichenfolge vorkommt. Anschließend wird das erste Zeichen abgeschnitten und der Vorgang wiederholt, bis keine Zeichen mehr übrig sind.

Das Band ist in 3-Zellen-Knoten unterteilt.

c 0 f

Dabei chandelt es sich um ein Zeichen der angegebenen Zeichenfolge und fum ein Flag, das entweder eins, negativ eins oder null sein kann. Nicht-Null-Flags werden zwischen die beiden Zeichen gesetzt, die gerade verglichen werden, und negative Flags sind für die Zellen nach dem Ende des aktuellen Präfixes und vor dem Beginn des aktuellen Suffixes (dh vor dem Index der aktuellen potenziellen Übereinstimmung) reserviert.

Das Ergebnis wird links von der Zeichenfolge gespeichert und aktualisiert, sobald eine Übereinstimmung gefunden wird.

(Die Zeichenfolge wird tatsächlich in umgekehrter Reihenfolge mit einem \x01angehängten Text verarbeitet .)

Mitch Schwartz
quelle
6

Gelee , 12 Bytes

œ-QL€
ŒṖÇ€FṀ

Probieren Sie es online!

Wie es funktioniert

ŒṖÇ€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
quelle
1
Alles Gute, Jelly, die ultimative Code-Golfsprache!
Nissa
œ-Qist wirklich ordentlich.
Lynn
5

Perl 6 , 36 Bytes

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

Versuch es

Erweitert:

{   # 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
quelle
5

Retina , 35 32 30 Bytes

Ziemlich coole Herausforderung.

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

Probieren Sie es online aus

Erläuterung:

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
quelle
Sie können zwei Bytes sparen, indem Sie M%`.als zweite Stufe verwenden.
Martin Ender
4

JavaScript (ES6), 79 68 66 Bytes

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>

Bearbeiten: 11 13 Bytes dank @Arnauld gespeichert.

Neil
quelle
4

Haskell , 79 Bytes

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

Probieren Sie es online!

Weizen-Assistent
quelle
2
Es sieht so aus, als ob das erste Argument von %eine nicht zusammenhängende aaaxayaa
Teilsequenz
Was @xnor gesagt hat. Ich denke, der rekursive Aufruf von a%dist falsch, aber auch unnötig. Was auch bedeutet, dass Sie maxanstelle von verwenden können maximum.
Ørjan Johansen
1
Ich denke, es zu ändern, a%dum ""%des zu beheben.
21.
Oh richtig, es wird immer noch benötigt (und der Ton), wenn aleer ist.
Ørjan Johansen
1
Ich denke, sum[1|(x,y)<-zip a c,x==y]kann anstelle von verwendet werden 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
quelle
2

Schale , 11 Bytes

L►L§fo↓2`xQ

Probieren Sie es online!

Hinweis: Hülsen sind neuer als diese Herausforderung.

Erläuterung

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
quelle
1

Mathematica, 75 65 Bytes

10 Bytes gespart durch @JingHwan min .

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

Anonyme Funktion. Nimmt einen String als Eingabe und gibt eine Zahl als Ausgabe zurück.

LegionMammal978
quelle
Ich glaube nicht, dass Sie den Anfang und das Ende brauchen, BlankNullSequence (___)wenn Overlaps->Alles da ist. Max@StringLength@StringCases[#,a___~~___~~a___:>a,Overlaps->All]&wäre in Ordnung.
JungHwan Min
@JungHwanMin Danke, habe es verwechselt mit StringReplace: P
LegionMammal978
1

Pyth - 16 Bytes

Ich muss Golf spielen, indem ich alle Saiten in Längen umwandle und die max.

eSlM+ksmft/dTd./

Test Suite .

Maltysen
quelle
1

Clojure, 112 Bytes

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

Schleifen zweimal über Zahlen 0bis n - 1( nLänge der Zeichenfolge), löschen von jZeichen und Aufteilen des Restes in "Anfang" - und "Ende" -Teile. Erstellt eine Menge aller Teilzeichenfolgen mit eder Länge bund prüft anhand dieser Funktion, ob bsie von dort gefunden werden. Liefert die Länge von bif found und sonst 0, gibt das Maximum dieser Werte zurück.

Wäre interessant, eine kürzere Version zu sehen.

NikoNyrh
quelle
1

Retina , 24 Bytes

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

Probieren Sie es online!

Ein Warmup für mich, um die neuen Funktionen von Retina 1 zu lernen.

Erläuterung

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

Eine Listenstufe (.*).*\1, die alle Übereinstimmungen für den regulären Ausdruck zurückgibt , der mit einem Muster der Form "ABA" übereinstimmt, wobei A und B zwei beliebige Teilzeichenfolgen sind (möglicherweise leer). Die zusätzlichen Optionen für diese Phase sind v: Berücksichtigt überlappende Übereinstimmungen und $ersetzt jede Übereinstimmung, bevor sie zurückgegeben wird. Die Substitution wird in der zweiten Zeile angezeigt und entspricht der Länge ( .) der ersten Erfassungsgruppe ( Dies wäre die Teilzeichenfolge "A" im vorherigen Beispiel.

N`

Wir haben jetzt alle Längen wiederholter Teilzeichenfolgen, diese Stufe sortiert sie einfach in numerischer Reihenfolge, von der kürzesten bis zur längsten.

G-1`

Schließlich Gbehält diese grep-Stufe ( ) nur das -1Ergebnis last ( ) bei, dh die Länge der längsten wiederholten Teilzeichenfolge.

Löwe
quelle
0

Javascript, 165 Bytes

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}

Testfälle

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
quelle
2
Willkommen bei Programming Puzzles & Code Golf. Leider gibt dies 2 für die Eingabe zurück ababcabcabcabcab, aber die Zeichenfolge cabcabwird wiederholt.
Dennis