Finden Sie die ursprüngliche Zeichenfolge ohne die Wiederholung ohne die Wiederholung in der Mitte

25

Manchmal ist es so, dass ich beim Schreiben eines Satzes abgelenkt bin und am Ende zweimal zweimal hintereinander die gleichen Wörter tippe.

Um sicherzustellen , dass andere Menschen davon nicht gestört werden, müssen Sie ein Programm schreiben, das dieses Problem behebt!

Aufgabe

Wenn Sie eine Eingabezeichenfolge angegeben haben (falls dies für Ihre Sprache von Bedeutung ist, können Sie eine reine ASCII-Eingabe ohne Zeilenvorschub annehmen) str, die irgendwo in der Mitte eine Teilzeichenfolge enthält, die zweimal unmittelbar hintereinander auftritt, geben Sie die Zeichenfolge mit einer Instanz davon zurück Teilzeichenfolge entfernt.

Geben Sie bei mehreren Möglichkeiten die kürzestmögliche Antwort zurück (dh wählen Sie die längste aufeinanderfolgende wiederholte Teilzeichenfolge aus und entfernen Sie diese).

Entfernen Sie bei mehreren gleich langen, sich wiederholenden Teilzeichenfolgen die erste (d. H. Die erste, die beim Lesen der Zeichenfolge von vorne nach hinten auftritt).

Sie können davon ausgehen, dass die Eingabe korrekt ist (dh immer eine sich wiederholende Teilzeichenfolge enthält), was dazu beitragen kann, die Eingabe zu verbessern.


Beispiele

  1. Eingang: hello hello world-> Ausgang: hello world.
  2. Eingang: foofoo-> Ausgang: foo. (Also: Ja, die Zeichenfolge besteht möglicherweise nur zweimal aus dem sich wiederholenden Teil.)
  3. Eingabe: aaaaa-> Ausgabe aaa:, da hier die am längsten wiederholte aufeinanderfolgende Teilzeichenfolge steht aa.
  4. Eingabe: Slartibartfast-> Dies ist keine gültige Eingabe, da sie keine aufeinanderfolgende wiederholte Teilzeichenfolge enthält, sodass Sie diesen Fall nicht behandeln müssen.
  5. Eingabe: the few the bar-> Dies ist eine weitere ungültige Eingabe, da der Wiederholungsteil unmittelbar auf den Originalteil folgen soll. In diesem Fall theund thedurch etwas anderes dazwischen getrennt, ist diese Eingabe ungültig.
  6. Eingang: ababcbc-> Ausgang: abcbc. Die zwei möglicherweise am längsten hintereinander wiederholten Teilzeichenfolgen sind abund bc. Wie bereits erwähnt, abist dies die richtige Antwort.
  7. Input: Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo. Ausgang: Buffalo buffalo buffalo buffalo Buffalo buffalo. (Beim durchgeführten Austausch muss die Groß- und Kleinschreibung beachtet werden.)
  8. Eingang: Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice couple of words twice in succession.-> Ausgang: Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice in succession.. Es wird nur die längste hintereinander wiederholte Teilzeichenfolge entfernt.

Ihr Code sollte so kurz wie möglich sein, da dies , damit die kürzeste Antwort in Bytes gewinnt. Viel Glück!

Qqwy
quelle
@manatwork Wenn Sie den ersten Satz Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice couple of words twice in succession.als Eingabe nehmen, sollte die Ausgabe sein Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice in succession.. Nur die am längsten gefundene Duplikation wird entfernt.
Qqwy
1
Ich schlage vor, einen Test hinzuzufügen, der zwei mögliche Ersetzungen aufweist, wobei die zweite länger ist als die erste. Ich vermute, die meisten Antworten werden diese nicht bestehen :)
etwa am
@ Aross Testfall 8 ist genau das :)
Qqwy
Sofern ich und mein Testcode nicht falsch sind, gibt es nur eine wiederholte Zeichenfolge.
am
@aross gibt es ein Doppel pinhappens
Qqwy

Antworten:

8

Perl 6 , 40 Bytes

{.subst: m:ex/(.*))>$0/.max(*.chars),''}

Versuch es

{
  .subst:             # substitute


    m                 # match
    :exhaustive
    /
      ( .* )          # any number of chars

      )>              # don't include the following in what is returned

      $0              # the first match again
    /.max( *.chars ), # find the first longest submatch


    ''                # substitute it with nothing
}
Brad Gilbert b2gills
quelle
8

Retina , 35 33 Bytes

Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.

(?=(.+)(\1.*))
$2¶$`
O$#`
$.&
G1`

Probieren Sie es online!

Erläuterung

Da Regex-Engines nach Übereinstimmungen von links nach rechts suchen, ist es nicht trivial, die längste Übereinstimmung zu finden, unabhängig von der Position. Dies kann mit den .NET-Bilanzkreisen durchgeführt werden, aber das Ergebnis ist ziemlich unangenehm lang:

1`((.)+)\1(?<=(?!.*((?>(?<-2>.)+).+)\3)^.*)
$1

Also nahm ich an, dass ich versuchen würde, dies zu vermeiden, indem ich einige andere Retina-Funktionen nutzte.

(?=(.+)(\1.*))
$2¶$`

Zunächst wenden wir im Wesentlichen alle möglichen Substitutionen an, eine in jeder Zeile. Dazu passen wir die Position vor einem Match an (anstelle des Matches selbst), um überlappende Matches zuzulassen. Dies geschieht, indem der echte Regex in einen Lookahead eingefügt wird. Dieser Lookahead erfasst dann den Rest mit Ausnahme des Duplikats, das in Gruppe 2 entfernt werden soll. Wir schreiben Gruppe 2 (Löschen des Duplikats), einen Zeilenvorschub und dann die gesamte Eingabe bis zum Match zurück, wodurch wir im Grunde eine neue Zeile erhalten ersetzt werden.

Am Ende haben wir eine Zeile für jede Übereinstimmung, wobei das entsprechende Duplikat entfernt wird. Am Ende gibt es auch wieder die volle Eingabe, ohne dass Ersetzungen vorgenommen werden.

Nachdem wir alle möglichen Substitutionen haben, wollen wir das kürzeste Ergebnis (das der längsten entfernten Wiederholung entspricht).

O$#`
$.&

Also sortieren wir zuerst die Zeilen nach Länge.

G1`

Und dann behalten wir nur die erste Zeile.

Martin Ender
quelle
Wow, diese Ersatztechnik ist wirklich clever!
Leo
6

Jelly , 22 19 Bytes

-2 Bytes dank Dennis (Argumentumkehr vermeiden, subtil redundantes Inkrement entfernen)

ẋ2³wȧ+¥J
ẆÇ€LÐṀḢṬœp

Probieren Sie es online!

Volles Programm (Es wurde ein Fehler gefunden, der darin besteht, dass ÐṀnicht mit der richtigen Arität gegenüber Dyaden vorgegangen wird. Dieser Fehler wird in Kürze behoben. Ich bin mir jedoch nicht sicher, ob hier ein kürzerer Code möglich ist).

Wie?

Findet das erste der längsten Segmente der Eingabe, sodass eine Wiederholung in der Eingabe vorhanden ist, und entfernt es aus der Eingabe.

ẋ2³wȧ+¥J - Link 1, removal indices for given slice if valid, else 0: slice, x
ẋ2       - repeat x twice, say y
  ³      - program input: s
   w     - index of first occurrence of y in s (1-based) or 0, say i
       J - range(length(x)): [1,2,3,...,length(x)]
      ¥  - last two links as a dyad
    ȧ    -     and (non-vectorising)
     +   -     addition: [1+i,2+i,3+i,...,length(x)+i] or 0
         - note: no need to decrement these since the last index will be the 1st index
         - of the repetition (thanks to Dennis for spotting that!)

ẆÇ€LÐṀḢṬœp - Main link: string, s
Ẇ          - all sublists of s (order is short to long, left to right, e.g. a,b,c,ab,bc,abc)
 Ç€        - call the last link (1) as a monad for €ach
    ÐṀ     - filter by maximal
   L       -     length
      Ḣ    - head: get the first (and hence left-most) one
       Ṭ   - untruth: make a list with 1s at the indexes given and 0s elsewhere
        œp - partition s at truthy indexes of that, throwing away the borders
           - implicit print
Jonathan Allan
quelle
6

JavaScript (ES6), 81 bis 74 Byte

f=
s=>s.replace(/(?=(.+)\1)/g,(_,m)=>r=m[r.length]?m:r,r='')&&s.replace(r,'')
<input oninput=o.textContent=f(this.value)><pre id=o>

Bearbeiten: 7 Bytes durch Stehlen von @ Arnauld's m[r.length]Trick gespeichert .

Neil
quelle
5

PowerShell , 87 Byte

param($s)([regex](([regex]'(.+)\1'|% *hes $s|sort L*)[-1]|% Gr*|% V*)[1])|% Re* $s '' 1

Probieren Sie es online! (alle Testfälle)

Erläuterung

Grundsätzlich starten wir von innen Matchesmit dem (.+)\1regulären Ausdruck, um alle Übereinstimmungsobjekte für die angegebene Zeichenfolge zurückzugeben. Der reguläre Ausdruck entspricht einer beliebigen Folge von Zeichen, die von ihm selbst gefolgt wird.

Dann werden die resultierenden Übereinstimmungsobjekte weitergeleitet sort, um nach ihrer LengthEigenschaft sortiert zu werden (abgekürzt als Platzhalter). Dies führt zu einem Array von Übereinstimmungen, die nach Länge aufsteigend sortiert sind. Indizieren Sie also mit [-1], um das letzte Element (das längste) zu erhalten. Der Wert dieser Übereinstimmung ist jedoch die Übereinstimmung, nicht die Gruppe, daher enthält sie die Wiederholung, sodass wir das Group-Objekt ( |% Gr*) und dann den Wert von that ( |% V*) abrufen , um die größte wiederholte Zeichenfolge zu erhalten. Das Gruppenobjekt ist eigentlich ein Array, weil Gruppe 0 immer die Übereinstimmung ist, aber ich möchte die tatsächliche Gruppe (1), also ist der resultierende Wert tatsächlich der Wert s , und daher wird indexiert, um das zweite Element zu erhalten [1]. Dieser Wert wird in ein reguläres Objekt selbst umgewandelt und anschließend in dasReplaceDie Methode wird für die ursprüngliche Zeichenfolge aufgerufen und durch nichts ersetzt, und nur die erste Übereinstimmung wird ersetzt ( |% Re* $s '' 1).

Briantist
quelle
5

Haskell , 101 Bytes

Hauptfunktion ist f, es dauert und gibt a zurück String.

l=length
a=splitAt
f s|i<-[0..l s-1]=[p++t|n<-i,(p,(r,t))<-fmap(a$l s-n).(`a`s)<$>i,r==take(l r)t]!!0

Probieren Sie es online!

Als ich das begann, habe ich importiert Data.Listund verwendet maximum, tails, initsund isPrefixOf. Irgendwie wurde das so. Aber ich habe es trotzdem geschafft, nur 11 Bytes zu entfernen ...

Anmerkungen

  • splitAt/ ateilt einen String an einem bestimmten Index.
  • s ist die Eingabezeichenfolge.
  • iDie folgenden Liste von Zahlen [0 .. length s - 1], die -1sind um zu arbeiten , dass splitAtSplits am Ende , wenn ein zu großen Index gegeben.
  • nlength sWenn das aktuelle Längenziel für den wiederholten Teil minus ist , wird es so gewählt, dass wir nicht zwei Zahlenlisten und / oder die Syntax mit abnehmender Wortzahl verwenden müssen.
  • p, rUnd tsind ein Dreifach Split s, wobei rder Teil wiederholt vorgesehen. Das fmapdortige verwendet das (,) String Functor, um eine Variable für einen Zwischensplit zu vermeiden.
  • !!0 Wählt das erste Element der Trefferliste aus.
Ørjan Johansen
quelle
4

Jelly , 23 21 Bytes

ṚẆUẋ€2ẇÐf¹ṪðLHḶ+w@Ṭœp

Vielen Dank an @ JonathanAllan für seine ṬœpIdee, die 2 Bytes gespart hat.

Probieren Sie es online!

Dennis
quelle
4

Mathematica, 63 60 59 Bytes

4 Bytes gespart durch Martin Ender .

#&@@StringReplaceList[#,a__~~a__->a]~SortBy~{StringLength}&

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

LegionMammal978
quelle
Dies scheint in Beispiel 6 nicht zu funktionieren - ~SortBy~StringLengthsortiert Strings alphabetisch, wenn ihre Längen gleich sind ...
Kein Baum
1
@ LegionMammal978 Der kürzere Fix ist keep SortByand wrap StringLengthin einer Liste, um eine stabile Sortierung zu erhalten.
Martin Ender
3

JavaScript (ES6), 70 Byte

s=>s.replace(s.match(/(.+)(?=\1)/g).reduce((p,c)=>c[p.length]?c:p),'')

Testfälle

Arnauld
quelle
Scheitert aaaabaaababer schön an reduce.
Neil
2

Dies sollte ein Kommentar sein, aber ich habe nicht genug Ruf, um ihn zu kommentieren. Ich möchte @Neil nur mitteilen, dass sein Code auf 77 Byte reduziert werden kann. Sie müssen keine Forward-Assertion in regulären Ausdrücken verwenden. Hier ist die reduzierte Version:

s=>s.replace(/(.+)\1/g,(_,m)=>(n=m.length)>l&&(l=n,r=m),l=0)&&s.replace(r,'')
TROLL
quelle
2
Hallo und willkommen bei PPCG! Sie können dies als Ihre eigene JavaScript-Antwort einreichen! Wenn Sie möchten, kann ich Ihren Beitrag bearbeiten und Ihnen zeigen, wie er aussehen soll.
NoOneIsHere
2
Ich muss die Forward-Behauptung verwenden, um den Fall überlappender Übereinstimmungen zu behandeln. aababist das kürzeste Beispiel dafür, wo Ihr Vorschlag fehlschlägt.
Neil
0

C # 169 Bytes

(s)=>{var x="";for(int i=0;i<s.Length-2;i++){for(int l=1;l<=(s.Length-i)/2;l++){var y=s.Substring(i,l);if(s.Contains(y+y)&l>x.Length)x=y;}}return s.Replace(x+x,x);}

Erläuterung

(s) => {                // Anonymous function declaration    
    var x = "";         // String to store the longest repeating substring found
    for (int i = 0; i < s.Length - 2; i++) {               // Loop through the input string
        for (int l = 1; l <= (s.Length - i) / 2; l++) {    // Loop through all possible substring lengths
            var y = s.Substring(i, l);
            if (s.Contains(y + y) & l > x.Length) x = y;   // Check if the substring repeats and is longer than any previously found
        }
    }
    return s.Replace(x + x, x);    // Perform the replacement
}

Dies ist der Brute-Force-Ansatz: Probieren Sie alle möglichen Teilzeichenfolgen aus, bis Sie die längste sich wiederholende Teilzeichenfolge finden. Zweifellos ist Regex effizienter, aber der Umgang mit Regex in C # ist in der Regel recht ausführlich.

Extragorey
quelle
Willkommen bei PPCG! Alle Antworten müssen entweder vollständige Programme oder aufrufbare Funktionen sein , nicht sicher Schnipsel mit Eingaben in fest codierten Variablen. Zeigen Sie außerdem die Version des Codes an, die Sie tatsächlich gezählt haben, wobei alle unnötigen Leerzeichen entfernt wurden. Sie können immer die lesbarere Version mit Einzug zusätzlich zu der vollständig golfenen Version einschließen.
Martin Ender
0

PHP, 84 82 Bytes

Anmerkung: Verwendet die IBM-850-Codierung.

for($l=strlen($argn);--$l&&!$r=preg_filter("#(.{0$l})\g-1#",~█╬,$argn,1););echo$r;

Laufen Sie wie folgt:

echo 'hello hello world' | php -nR 'for($l=strlen($argn);--$l&&!$r=preg_filter("#(.{0$l})\g-1#",~█╬,$argn,1););echo$r;';echo
> hello world

Erläuterung

for(
  $l=strlen($argn);   # Set $l to input length.
  --$l   &&           # Decrement $l each iteration until it becomes 0.
  !$r=preg_filter(    # Stop looping when preg_filter has a result
                      # (meaning a successful replace).
    "#(.{0$l})\g-1#", # Find any character, $l times (so the longest
                      # match is tried first), repeated twice.
    ~█╬,              # Replace with $1: first capture group, removing the
                      # duplicate.
    $argn,
    1                 # Only replace 1 match.
  );
);
echo$r;               # Print the result of the (only) successful
                      # search/replace, if any.

Optimierungen

  • 2 Byte gespeichert, da die wiederholte Teilzeichenfolge keine Mindestlänge hat
aross
quelle