Czasami zdarza się, że podczas pisania zdania jestem rozkojarzony i w końcu wpisuję te same słowa dwa razy dwa razy pod rząd.

Aby upewnić się, że nie przeszkadza to innym, Twoim zadaniem jest napisanie programu, który rozwiąże ten problem!

Zadanie

Biorąc pod uwagę ciąg wejściowy (jeśli ma to znaczenie dla twojego języka, możesz założyć, że wejście zawiera tylko ASCII, które nie zawiera kanałów.) str, Które zawiera gdzieś pośrodku podciąg, który występuje dwa razy z rzędu, zwróć ciąg z jedną instancją tego podciąg usunięty.

W przypadku wielu możliwości zwróć najkrótszą możliwą odpowiedź (to znaczy wybierz najdłuższy podciąg powtarzający się i usuń tę).

W przypadku wielu, równie długich kolejnych powtarzających się podciągów, usuń pierwszy (to znaczy pierwszy napotkany podczas czytania ciągu od przodu do tyłu).

Możesz założyć, że dane wejściowe są poprawne (tzn. Zawsze zawierają kolejne powtarzające się podciągi), co może pomóc w obniżeniu ich golfa.

Przykłady

1. Wejście: hello hello world-> Wyjście: hello world.
2. Wejście: foofoo-> Wyjście: foo. (Więc: Tak, ciąg może składać się tylko z powtarzającej się części dwa razy).
3. Dane wejściowe: aaaaa-> Dane wyjściowe:, aaaponieważ znajduje się tutaj najdłuższy powtarzający się podciąg aa.
4. Dane wejściowe: Slartibartfast-> To nie jest poprawne wejście, ponieważ nie zawiera kolejnych powtarzających się podciągów, więc nie musisz zajmować się tą sprawą.
5. Wejście: the few the bar-> Jest to kolejne nieprawidłowe wejście, ponieważ powtarzająca się część powinna natychmiast następować po części oryginalnej. W tym przypadku, thei thesą oddzielone przez coś innego w międzyczasie, więc to wejście jest nieprawidłowy.
6. Wejście: ababcbc-> Wyjście: abcbc. Dwa możliwe najdłuższe kolejne powtarzające się podciągi to abi bc. Jak abnapotkano wcześniej w ciągu, ta odpowiedź jest poprawna.
7. Wejście: Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo. Wyjście: Buffalo buffalo buffalo buffalo Buffalo buffalo. (W wykonanej zamianie rozróżniana jest wielkość liter).
8. Wejście: 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.-> Wyjście: Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice in succession.. Usuwane są tylko najdłuższe kolejne powtarzające się podciągi.

Twój kod powinien być możliwie jak najkrótszy, ponieważ jest to gra w golfa , więc wygrywa najkrótsza odpowiedź w bajtach. Powodzenia!

Perl 6 , 40 bajtów

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

Spróbuj

{
  .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
}

Siatkówka , 35 33 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1.

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

Wypróbuj online!

Wyjaśnienie

Ponieważ silniki wyrażeń regularnych szukają dopasowań od lewej do prawej, znalezienie najdłuższego dopasowania bez względu na pozycję nie jest trywialne. Można to zrobić za pomocą grup równoważących .NET, ale wynik jest raczej nieprzyjemnie długi:

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

Pomyślałem więc, że spróbuję tego uniknąć, wykorzystując inne funkcje Retina.

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

Zaczynamy od zastosowania zasadniczo wszystkich możliwych podstawień, po jednym w każdym wierszu. Aby to zrobić, dopasowujemy pozycję przed meczem (zamiast samego meczu), aby umożliwić nakładanie się meczów. Odbywa się to poprzez umieszczenie prawdziwego wyrażenia regularnego w spojrzeniu w przyszłość. Ten lookahead następnie przechwytuje pozostałe oprócz duplikatu, który chcemy usunąć w grupie 2. Zapisujemy grupę 2 (usuwając duplikat), wysuw liniowy, a następnie całe dane wejściowe aż do dopasowania, co daje nam zasadniczo świeżą linię do być podstawionym.

Na koniec będziemy mieć jeden wiersz dla każdego dopasowania, z usuniętym odpowiednim duplikatem. Na koniec będzie też ponownie pełne wejście bez dokonywania żadnych zmian.

Teraz, gdy mamy wszystkie możliwe podstawienia, chcemy uzyskać najkrótszy wynik (który odpowiada najdłużej usuniętemu powtórzeniu).

O$#`
$.&

Więc najpierw sortujemy linie według długości.

G1`

A potem zachowujemy tylko pierwszą linię.

Galaretka , 22 19 bajtów

-2 bajty dzięki Dennisowi (unikaj zamiany argumentów, usuń subtelnie zbędny przyrost)

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

Wypróbuj online!

Pełny program (znaleziono błąd ÐṀpolegający na tym, że nie działa z odpowiednią aranżacją w stosunku do diadów, co zostanie wkrótce naprawione; chociaż nie jestem pewien, czy może to zrobić tutaj krótszy kod).

W jaki sposób?

Znajduje pierwszy z najdłuższych segmentów danych wejściowych w taki sposób, że w danych wejściowych istnieje powtórzenie i usuwa je z danych wejściowych.

ẋ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

JavaScript (ES6), 81 74 bajtów

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>

Edycja: Zapisano 7 bajtów, kradnąc m[r.length]sztuczkę @ Arnauld .

PowerShell , 87 bajtów

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

Wypróbuj online! (wszystkie przypadki testowe)

Wyjaśnienie

Zaczynając od środka, w zasadzie uruchamiamy Matchesz (.+)\1wyrażeniem regularnym, aby zwrócić wszystkie obiekty dopasowania dla określonego ciągu. Wyrażenie regularne pasuje do dowolnej sekwencji znaków, po której następuje sam.

Następnie powstałe obiekty dopasowania są wpompowywane w sortcelu posortowania według ich Lengthwłaściwości (skróconej do symbolu wieloznacznego). Powoduje to tablicę dopasowań posortowaną według długości, rosnąco, więc indeksuj za pomocą, [-1]aby uzyskać ostatni element (najdłuższy). Wartość tego dopasowania jest jednak dopasowaniem, a nie grupą, więc obejmuje powtórzenie, więc pobieramy obiekt Group ( |% Gr*), a następnie wartość tego ( |% V*), aby uzyskać największy powtarzany ciąg. Rzecz w tym, że obiekt grupy jest w rzeczywistości tablicą, ponieważ grupa 0 jest zawsze zgodna, ale chcę rzeczywistą grupę (1), więc wartość wynikowa jest w rzeczywistości wartością s , stąd indeksowanie w celu uzyskania drugiego elementu [1]. Ta wartość jest rzutowana na sam obiekt wyrażenia regularnego, a następnieReplaceMetoda jest wywoływana w stosunku do oryginalnego ciągu, zamieniając na nic i zastępowane jest tylko pierwsze dopasowanie ( |% Re* $s '' 1).

Haskell , 101 bajtów

Główną funkcją jest f, bierze i zwraca a 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

Wypróbuj online!

Kiedy zacząłem to, że importowane Data.Listi wykorzystywane maximum, tails, initsi isPrefixOf. Jakoś to się zmieniło w to. Ale nadal udało mi się tylko zgolić 11 bajtów ...

Notatki

• splitAt/ adzieli ciąg pod danym indeksem.
• s jest łańcuchem wejściowym.
• ito lista liczb [0 .. length s - 1], która -1ma obejść splitAtpodział na końcu, jeśli ma zbyt duży indeks.
• njest length sminus bieżąca długość celu dla powtarzanej części, jest ona wybrana w ten sposób, abyśmy nie musieli używać dwóch list liczb i / lub pełnej składni listy malejącej.
• p, ri tsą trójdrożnym podziałem s, z rzamierzoną powtarzaną częścią. fmapNie używa (,) String Functorw celu uniknięcia zmiennych dla pośredniego podziale.
• !!0 wybiera pierwszy element z listy dopasowań.

Galaretka , 23 21 bajtów

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

Dzięki @JonathanAllan za Ṭœppomysł, który oszczędził 2 bajty.

Wypróbuj online!

Mathematica, 63 60 59 bajtów

^{4 bajty zapisane dzięki Martinowi Enderowi .}

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

Funkcja anonimowa. Pobiera ciąg jako dane wejściowe i zwraca ciąg jako dane wyjściowe.

JavaScript (ES6), 70 bajtów

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

Przypadki testowe

let f =

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

console.log(f("hello hello world"))
console.log(f("foofoo"))
console.log(f("aaaaa"))
console.log(f("ababcbc"))
console.log(f("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."))

To powinien być komentarz, ale nie mam wystarczającej reputacji, aby móc komentować. Chcę tylko powiedzieć @Neil, że jego kod można zmniejszyć do 77 bajtów. W wyrażeniach regularnych nie trzeba używać potwierdzenia do przodu. Oto zmniejszona wersja:

s=>s.replace(/(.+)\1/g,(_,m)=>(n=m.length)>l&&(l=n,r=m),l=0)&&s.replace(r,'')

C #, 169 bajtów

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

Wyjaśnienie

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

Jest to podejście typu brute-force: wypróbuj każdy możliwy podciąg, aż znajdziemy najdłuższy powtarzający się podciąg. Niewątpliwie Regex jest bardziej wydajny, ale radzenie sobie z nim w języku C # bywa dość szczegółowe.

PHP, 84 82 bajtów

Uwaga: używa kodowania IBM-850.

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

Uruchom tak:

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

Wyjaśnienie

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.

Poprawki

• Zapisano 2 bajty, ponieważ nie ma minimalnej długości powtarzanego podłańcucha