Napisz program lub funkcję, która, biorąc pod uwagę dwa łańcuchy ASCII A
i B
, wygeneruje łańcuchy A'
i B'
gdzie wspólne podciągi są odwrócone w ich miejsce. Proces wyszukiwania A'
jest następujący:
A'
jest początkowo pusty.- Jeśli pierwszy znak
A
jest wB
, znajdź najdłuższy przedrostek,A
którego jest podłańcuchemB
. Usuń ten prefiks zA
i dodaj jego odwrócenie doA'
. - W przeciwnym razie usuń ten pierwszy znak z
A
i dodaj go doA'
. - Powtarzaj kroki 2-3, aż
A
będzie pusty.
Znalezienie B'
odbywa się podobnie.
Przykład
Rozważmy ciągi A = "abc bab"
i B = "abdabc"
. Bo A'
tak się dzieje:
A = "abc bab"
: Pierwszy znak"a"
znajduje się w B, a najdłuższy prefiks A w B to"abc"
. Usuwamy ten prefiks z A i dodajemy jego odwrócenie"cba"
do A '.A = " bab"
: Pierwszy znak" "
nie znajduje się w B, więc usuwamy ten znak z A i dodajemy go do A '.A = "bab"
: Pierwszy znak"b"
znajduje się w B, a najdłuższy prefiks A w B to"b"
. Usuwamy ten prefiks z A i dodajemy jego odwrócenie (które jest nadal"b"
) do A '.A = "ab"
: Pierwszy znak"a"
znajduje się w B, a najdłuższy prefiks A w B to"ab"
. Usuwamy ten prefiks z A i dodajemy jego odwrócenie"ba"
do A '.A = ""
: A jest puste, więc przestajemy.
Tak otrzymujemy A' = "cba" + " " + "b" + "ba" = "cba bba"
. W przypadku B 'proces jest podobny:
B = "abdabc" -> "a" in A, remove prefix "ab"
B = "dabc" -> "d" not in A, remove "d"
B = "abc" -> "a" in A, remove prefix "abc"
Tak otrzymujemy B' = "ba" + "d" + "cba" = "badcba"
.
Na koniec zwracamy dwa ciągi, tj
(A', B') = ("cba bba", "badcba")
Przypadki testowe
"abc bab", "abdabc" -> "cba bba", "badcba"
"abcde", "abcd bcde" -> "dcbae", "dcba edcb"
"hello test", "test banana" -> "hello tset", "tset banana"
"birds flying high", "whistling high nerds" -> "bisdr flyhgih gni", "wihstlhgih gni nesdr"
Najkrótszy kod w bajtach wygrywa.
"cba bba", "badcba"
cytowań i przecinków?Odpowiedzi:
Pyth, 29 bajtów
Uprząż testowa.
Format wejściowy to:
Dane wyjściowe to:
źródło
Haskell,
120111 bajtówPrzebiegi testowe:
źródło
SWI-Prolog, 312 bajtów
Przykład:
a("birds flying high","whistling high nerds",X,Y).
wyjściaDroga, droga zbyt długa rozwiązanie, które pokazują, jak idzie zbyt rozwlekły Prolog jest gdy ma do czynienia ze strun. Może być możliwe skrócenie tej rzeczy za pomocą tablic kodów (
`birds flying high`
) zamiast strings ("birds flying high"
).źródło
Python 2.7,
169156152141 bajtówFunkcja
m
przyjmuje 2 łańcuchy jako dane wejściowe i wywołujeb
funkcję dwukrotnie, co powoduje faktyczne przetwarzanie zgodnie ze specyfikacją.Demo tutaj .
Testowanie -
WYJŚCIA:
PS: Dzięki orlp za rozwiązanie
next()
źródło
m=lambda A,B:(b(A,B),b(B,A))
while len(A)>0
justwhile A
. Podobnieif len(p)>0
staje sięif p
.if len(p)
może być równieżif p
. (Już powiedziałem wyżej, ale przegapiłeś to.)len(p)>0
sięlen(p)
. Dzięki za to :)while A:j=next((j for j in range(len(A),0,-1)if A[:j]in B),1);C+=A[:j][::-1];A=A[j:]
.