Wyjaśnienie
Dwa ciągi można potasować, przerywając ich litery, aby utworzyć nowy ciąg, podobnie jak dwa stosy kart można potasować, tworząc pojedynczy stos.
Na przykład ciągi HELLO
i WORLD
mogą być tasowane, aby utworzyć HWEOLRLLOD
, lub HEWORLLLDO
, może po prostu HELLOWORLD
.
To nie jest tasowanie, jeśli pierwotna kolejność liter nie zostanie zachowana. Na przykład, D
w WORLD
nigdy nie może pojawić się, zanim R
po tasuje. Oznacza to, że EHLLOWRDLO
na przykład nie jest tasowaniem HELLO
i WORLD
, mimo że zawiera wszystkie oryginalne litery.
Sznurek jest przetasowaniem bliźniaków, jeśli można go uformować przez tasowanie dwóch identycznych strun. Na przykład ABACBDECDE
jest tasowaniem bliźniaków, ponieważ można go utworzyć przez tasowanie ABCDE
i ABCDE
. DBEACBCADE
nie jest tasiemkiem bliźniaków, ponieważ nie można go utworzyć przez tasowanie dwóch identycznych strun.
Szczegóły programu
Biorąc pod uwagę ciąg wejściowy, wypisuje, 0
jeśli nie jest to losowy los bliźniaków, i wyprowadza jeden z bliźniaczych ciągów, jeśli jest to losowy los bliźniaków.
Możesz założyć, że łańcuch wejściowy ma długość od czterech do dwudziestu znaków i składa się wyłącznie z wielkich liter alfabetu. Powinien być w stanie działać w rozsądnym czasie, powiedzmy, poniżej 10 minut.
To jest golf golfowy, więc wygrywa najkrótsze rozwiązanie.
Przykład I / O
> ABACBDECDE
ABCDE
> DBEACBCADE
0
> FFFFFF
FFF
> FFGGG
0
> ABBA
0
> AABB
AB
> AABAAB
AAB
źródło
that the input string has a length inclusively between four and twenty characters
i nie mów mi: „nigdy nie ufaj wejściom użytkownika!”, „Nigdy nie ufaj specyfikacji!”FFGGG
aby był spójny.Odpowiedzi:
Haskell, 114
Nie golfowany:
Wyjaśnienie:
Większość pracy jest wykonywana w
partitions
funkcji. Działa poprzez rekurencyjne generowanie wszystkich partycji(a, b)
ogona listy, a następnie za pomocą monady listy, aby dołączyć element początkowyx
do każdej z nich i zebrać wszystkie wyniki.findMatch
działa poprzez filtrowanie tej listy, aby pozostały tylko partycje, w których podsekwencje są równe. Następnie zwraca pierwszą podsekwencję w pierwszej partycji. Jeśli nie pozostanie, lista jest pusta, więc"0"
zamiast tego zwracana jest dołączona na końcu.main
po prostu odczytuje dane wejściowe, przekazuje je przez te dwie funkcje i drukuje.źródło
R, 113 znaków
Ungolfed (i zamiast tego funkcja, która pobiera ciąg):
Rozwiązanie opiera się na
combn
funkcji, która generuje wszystkie kombinacje indeksów jako kolumny w macierzy.apply
następnie stosuje funkcję do każdej kolumny (wymiaru2
) w macierzy i zwraca wektor ciągów lub zer.max
następnie znajdź największy ciąg (który przebija 0).Fajną cechą w R jest możliwość wybrania podzbioru wektora podanego wektorem indeksów, a następnie wybrania dopełnienia tego podzbioru przez zanegowanie indeksów:
x[i] == x[-i]
źródło
Mathematica, 87
Jest to bezpośrednio oparte na poście Hammara, ale mam nadzieję, że jest wystarczająco wyraźne, aby zasługiwać na opublikowanie.
Test:
źródło
re
używając głębokości pierwszego wyszukiwania rekurencyjnego
Mogę przyspieszyć dzięki
int i = min(a.length,b.length);if(a[0..i]!=b[0..i])return "0";
klauzuli ochronnejźródło
void main(){writeln(c("ABCADABCAD"));}
- tylko inną wersją D, moja wina, coś jeszcze? Co z „ABCABCA”?Ruby, 89 znaków
Ten kod implementuje prosty algorytm wyszukiwania rekurencyjnego. Dane wejściowe należy podać na STDIN.
źródło
Perl, 68 znaków
Zakłada się, że łańcuch wejściowy znajduje się w
$_
zmiennej, a wynikiem jest wartość wyrażenia. Końcowe znaki nowej linii w danych wejściowych są ignorowane. Możesz uruchomić to z wiersza poleceń w następujący sposób:Ten kod wykorzystuje silnik wyrażeń regularnych Perla (a zwłaszcza jego funkcję wykonywania kodu osadzonego ) w celu wykonania śledzenia wstecznego. Zasadniczo dopasowuje ciąg wejściowy do
^((.+))+$
wyrażenia regularnego, śledząc nieparzyste i parzyste podelementy w$x
i$,
, i odrzuca dopasowanie na końcu, jeśli dwa nie są równe.źródło
AABAAB
?AABAAB
jest to łatwy przypadek dla tego rozwiązania, ponieważ grupa zewnętrzna musi dopasować się tylko dwa razy. Zajęło mi to dużo więcej czasu, aby dobrze sobie z tym poradzićAABB
.)Python, 168 znaków
źródło