Jak kompatybilne są moje ciągi?

12

Wprowadzenie

Rozważ dwa ciągi A i B o tej samej długości L oraz liczbę całkowitą K ≥ 0 . Na potrzeby tego wyzwania mówimy, że ciągi są kompatybilne z K , jeśli istnieje ciąg C o długości K taki, że A jest ciągłym podciągiem konkatenacji BCB . Zauważ, że A jest podciągiem BAB , więc A i B są zawsze kompatybilne z L (ale mogą być również kompatybilne z K dla niektórych innych K <L ).

Wejście

Twoje dane wejściowe to dwa ciągi o tej samej długości dodatniej, składające się z wielkich i małych liter ASCII.

Wynik

Twoje wyjście powinno być najniższą nieujemną liczbą całkowitą K, tak aby wejścia były kompatybilne z K.

Przykład

Rozważ dane wejściowe

A = HHHHHH
B = HHttHH

Nie są one zgodne z 0, ponieważ A nie jest podłańcuchem HHttHHHHttHH. Nie są również kompatybilne z 1, ponieważ A nie jest podciągiem, HHttHH#HHttHHbez względu na to, która litera zostanie umieszczona na #. Jednak A jest podłańcuchem HHttHHHHHHttHH, gdzie C jest łańcuchem dwuliterowym HH. Zatem wejścia są kompatybilne z 2, a prawidłowe wyjście to 2.

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

Warunek zgodności jest symetryczny, więc zamiana dwóch wejść nie powinna zmieniać wyjścia.

E G -> 1
E E -> 0
aB Bc -> 1
YY tY -> 1
abcd bcda -> 0
abcXd bxcda -> 4
Hello Hello -> 0
Hello olHel -> 1
aBaXYa aXYaBa -> 1
aXYaBa aBaXYa -> 1
HHHHHH HHttHH -> 2
abcdab cdabcd -> 2
XRRXXXXR XRXXRXXR -> 4
evveeetev tetevevev -> 7
vzzvzJvJJz vJJvzJJvJz -> 10
JJfcfJJcfJfb JcfJfbbJJJfJ -> 5
GhhaaHHbbhGGH HHaaHHbbGGGhh -> 9
OyDGqyDGDOGOGyG yDGqOGqDyyyyOyD -> 12
ffKKBBpGfGKpfGpbKb fGpbKbpBBBffbbbffK -> 9
UZuPPZuPdVdtuDdDiuddUPtUidtVVV dtUPtUidtVVVtDZbZZPuiUZuPPZuPd -> 21

Tabela liderów

Oto fragment kodu, aby wygenerować tabelę wyników i listę zwycięzców według języka. Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka formularza

## Language, N bytes

Możesz zachować stare wyniki w nagłówku, używając tagów przekreślenia: <s>57</s>pojawi się jako 57 .

Zgarb
źródło

Odpowiedzi:

8

Pyth, 16 lat

lhf}QjT,vzvz+k.:

Znajdź najkrótszy podciąg A, który po wstawieniu między dwie kopie B daje ciąg zawierający A.

Może to być dwa bajty krótsze, jeśli w drugim wierszu nie ma cudzysłowów, ale to dziwne?

Pakiet testowy

FryAmTheEggman
źródło
4

Python 3, 155 168 157 bajtów

Łącznie to długość A. Porównaj początek Ado końca Bi odejmij to od sumy. Porównaj początek Bdo końca Ai odejmij to od sumy. Zwraca wartość bezwzględną sumy, chyba że suma jest równa długości, w którym to przypadku zwraca 0.

def f(A,B):
    T=L=len(A)
    C=D=1
    for i in range(L,0,-1):
        if A[:i]==B[-i:]and C:
            T,C=T-i,0
        if A[-i:]==B[:i]and D:
            T,D=T-i,0
    return (0,abs(T))[T!=-L]

Edycja: załatw f("abcdab","cdabcd")==2sprawę

Nieliniowe Owoce
źródło
3
Niestety, to nie działa, dla f("abcdab", "cdabcd")których powinno być 2.
Neil
@Neil Good catch. Dodam to do przypadków testowych.
Zgarb
@ mEQ5aNLrK3lqs3kfSa5HbvsTWe0nIu Patrzyłem na obraz i myślałem: „To fajny pomysł na debugowanie, aby używać emoji, ale nie widzę błędu ...”. Myślę, że ten dodatek siałby spustoszenie na tej stronie.
NielinioweOwoce
3

Siatkówka , 49 bajtów

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

Wypróbuj online! (Nieznacznie zmodyfikowany, aby uruchomić wszystkie testy jednocześnie).

Sztuka polega na tym, że musimy cofnąć się do części A, w której się nie znajdujemy B, a do tej pory nie znalazłem sposobu na zrobienie tego bez dość irytujących spojrzeń i równoważenia grup.

Martin Ender
źródło
3

Jolf, 40 bajtów

Wά)Ζ0W<ζli)? h++i]Iζ+ζniIoά0nΖhζ}onhn}wn

Spróbuj!

Jestem całkiem nowy dla Jolfa, wiele się nauczyłem, rozgryzając to. Wydaje się to trochę niezręczne, ale prawdopodobnie można by dalej grać w golfa. Nawet strąciłem 2 bajty podczas pisania tego wyjaśnienia.

Wyjaśnienie:

  Wά)                                      While ά (initialized to 16)
     Ζ0                                    Set ζ to 0
       W<ζli)                              While ζ < length(A)
             ? h++i]Iζ+ζniIoά0n            Set ά to 0 if (A + a substring from B of length n + A) contains B
                               Ζhζ         Increment ζ
                                  }onhn    Increment n (initialize to 0
                                       }wn Decrement n and print
puchnie
źródło
Nie próbowałem na poważnie, i może to być optymalne rozwiązanie, ale sugeruję próbę mapowania poza zakresami. ( s0zlida ci tablicę [0 ... długość i], jeśli chcesz spróbować tego podejścia.)
Conor O'Brien
@ Cᴏɴᴏʀ O'Bʀɪᴇɴ Hmm, rzucę okiem ... czy jest też polecenie if, które wyskoczyłem podczas przeglądania dokumentacji / źródła, czy jest to jedyna opcja? z nieistotnym trzecim argumentem?
puchnie
?jest najbliżej jeśli jest w Jolf. To jak trójka, jeśli. ?ABCs returns B` jeśli a jest prawdą, i Cinaczej.
Conor O'Brien
2

JavaScript (ES6), 110 bajtów

(a,b)=>{for(i=0;;i++)for(j=i;j<=a.length;j++)if(b.startsWith(a.slice(j))&&b.endsWith(a.slice(0,j-i)))return i}

Działa poprzez krojenie coraz dłuższych kawałków ze środka, aaż dopasują się do dwóch końców b. Pętla nie jest nieskończona, ponieważ zatrzyma się przed lub wcześniej i == a.length.

Neil
źródło