W tym wyzwaniu Twoim zadaniem jest zlokalizowanie podciągów o określonej strukturze.
Wejście
Twoje dane powinny składać się z dwóch niepustych ciągów alfanumerycznych, wzorca p
i tekstu t
. Chodzi o to, że każdy znak p
reprezentuje ciągłe niepuste podciągi, t
które występują obok siebie, i p
reprezentuje ich konkatenację. Identyczne znaki odpowiadają identycznym podciągom; na przykład wzór aa
reprezentuje dowolny niepusty kwadrat (ciąg uzyskany przez połączenie krótszego ciągu z samym sobą). W ten sposób wzór aa
może dopasować podciąg byebye
, z każdym a
dopasowaniem bye
.
Wynik
Jeśli tekst t
zawiera podłańcuch, który p
pasuje, wówczas wynikiem będzie podłańcuch z dwukropkami :
wstawionymi między ciągi znaków odpowiadające znakom p
. Na przykład, jeśli mamy t = byebyenow
i p = aa
, to bye:bye
jest akceptowalny wynik. Może istnieć kilka opcji dopasowania podłańcucha, ale wypisujesz tylko jedną z nich.
Jeśli t
nie zawiera pasującego podciągu, twoja praca będzie smutną miną :(
.
Zasady i wyjaśnienia
Różne znaki p
mogą odpowiadać identycznym podciągom, więc p = aba
mogą pasować do łańcucha AAA
. Zauważ, że znaki muszą odpowiadać niepustym ciągom; w szczególności, jeśli p
jest dłuższy niż t
, wyjście musi być :(
.
Możesz napisać pełny program lub funkcję, a także zmienić kolejność dwóch wejść. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.
Przypadki testowe
Podany w formacie pattern text -> output
. Zauważ, że mogą istnieć inne dopuszczalne wyniki.
a Not -> N
aa Not -> :(
abcd Not -> :(
aaa rerere -> re:re:re
xx ABAAAB -> A:A
MMM ABABBAABBAABBA -> ABBA:ABBA:ABBA
x33x 10100110011001 -> 10:1001:1001:10
abcacb 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> c:a0aa:0c:c:0c:a0aa
abccab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> a:a:0c0:0c0:a:a
abcbcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> :(
abcbdcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> 00:c:ca0aa0c:c:0:ca0aa0c:00:c
źródło
O(2^((n * (n + 1))/2))
: POdpowiedzi:
Python, 207 bajtów
Zadzwoń z
g(pattern, string)
Wykorzystuje
re
moduł do wykonywania większości prac.źródło
JavaScript (SpiderMonkey) (ES5.1), 198 bajtów
Ponieważ ES6 został wydany w czerwcu 2015 r., Publikuję wersję kodu ES5.1 wraz z odpowiednikiem ES6, ale deklaruję wersję ES5.1 jako główną odpowiedź.
Chciwy mecz, więc pierwszy przypadek zwraca „Nie” zamiast „N”.
Wypróbuj online!
JavaScript (Node.js) (ES6), 141 bajtów
Wypróbuj online!
Bierze argumenty w składni curry:
f(a)(b)
Objaśnienie (i bez golfa):
źródło
Brachylog , 35 bajtów
Wypróbuj online!
On nie całkiem małych nakładów, bardzo wolno. W rzeczywistości nie zrobiłem powolnego szóstego przypadku testowego, ale nie z powodu braku prób. (Prawdopodobnie z powodu brutalnego wymuszania każdej partycji każdego podłańcucha, zaczynając od największego, a następnie sprawdzając, czy jest on zgodny.) Pobiera dane wejściowe jako listę
[pattern,string]
.Skrócone i podzielone wyjaśnienie:
sᵗ~cᵗX
X jest wzorcem sparowanym z partycją podłańcucha ciągu wejściowego.
lᵛ
Wzór i partycja mają tę samą liczbę elementów.
Xzdz≠ʰ
Żadne dwie unikalne
pattern char, matched substring
pary nie mają wspólnego wzoru. Oznacza to, że żaden znak wzorca nie jest odwzorowywany na wiele podciągów, chociaż wiele znaków wzorca może być odwzorowywanych na jeden podciąg.Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("
Dane wyjściowe to elementy partycji połączone dwukropkami, chyba że nic nie można zrobić, w takim przypadku tak jest
:(
zamiast tego.Objaśnienie monolityczne:
źródło