Насколько совместимы мои строки?

12

Вступление

Рассмотрим две строки A и B одинаковой длины L и целое число K ≥ 0 . В целях этой задачи мы говорим, что строки совместимы с K , если существует строка C длины K такая, что A является непрерывной подстрокой конкатенации BCB . Обратите внимание, что A является подстрокой BAB , поэтому A и B всегда L- совместимы (но также могут быть K- совместимыми для некоторых других K <L ).

вход

Ваши входные данные представляют собой две строки одинаковой положительной длины, состоящие из прописных и строчных букв ASCII.

Выход

Ваш вывод должен быть наименьшим неотрицательным целым числом K , так что входы являются K- совместимыми.

пример

Рассмотрим входы

A = HHHHHH
B = HHttHH

Они не являются 0-совместимыми, потому что A не является подстрокой HHttHHHHttHH. Они также не являются 1-совместимыми, потому что A не является подстрокой HHttHH#HHttHHнезависимо от того, какая буква помещена на #. Однако A является подстрокой HHttHHHHHHttHH, где C является двухбуквенной строкой HH. Таким образом, входы 2-совместимы, и правильный выход 2.

Правила и оценки

Вы можете написать полную программу или функцию. Побеждает меньшее количество байтов, и стандартные лазейки запрещены.

Контрольные примеры

Условие совместимости симметрично, поэтому замена двух входов не должна изменить выход.

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

Leaderboard

Вот фрагмент стека для генерации списка лидеров и списка победителей по языкам. Чтобы убедиться, что ваш ответ появляется, начните с заголовка формы

## Language, N bytes

Вы можете сохранить старые результаты в заголовке с помощью зачеркнутых тегов: <s>57</s>будет отображаться как 57 .

Показать фрагмент кода

code-golf string Zgarb
источник

Ответы:

8

Пиф, 16

lhf}QjT,vzvz+k.:

Найдите самую короткую подстроку A, которая при вставке между двумя копиями B приводит к строке, содержащей A.

Это может быть на два байта короче, если во второй строке нет кавычек, но это странно?

Тестирование

FryAmTheEggman
источник
4

Python 3, 155 168 157 байт

Общая длина A. Сравните начало Aс концом Bи вычтите это из общего. Сравните начало Bс концом Aи вычтите это из общего. Вернуть абсолютное значение итога, если сумма не равна длине, в этом случае вернуть 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]

Редактировать: обрабатывать f("abcdab","cdabcd")==2дело

NonlinearFruit
источник
3
К сожалению, это не работает, для f("abcdab", "cdabcd")чего должно быть 2.
Нил
@Neil Хороший улов. Я добавлю это к тестам.
Згарб
1
Это было неожиданно. ( Global Twitch Emotes )
Ф. Джордж
@ mEQ5aNLrK3lqs3kfSa5HbvsTWe0nIu Я смотрел на изображение и думал: «Это отличная идея отладчика для использования смайликов, но я не вижу ошибки ...». Я думаю, что это дополнение нанесло бы ущерб этому сайту.
Нелинейный
3

Сетчатка , 49 байт

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

Попробуйте онлайн! (Немного изменен для запуска всех тестов одновременно.)

Хитрость заключается в том, что мы должны возвратиться на ту часть , Aчто мы не находим в B, и до сих пор я не нашел способ сделать это без раздражающих , а lookarounds и балансирующих групп.

Мартин Эндер
источник
3

Джольф, 40 байт

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

Попытайся!

Я совсем новичок в Джольфе, многому научился, выясняя это. Кажется, немного неловко, но все же, вероятно, можно было бы играть дальше. Даже сбил 2 байта при написании этого объяснения.

Объяснение:

  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
разбухает
источник
Я не пытался всерьез, и это может быть оптимальным решением, но я предлагаю попробовать сопоставить диапазоны. ( s0zliдаст вам массив [0 ... length i], если вы хотите попробовать этот подход.)
Конор О'Брайен,
@ Cᴏɴᴏʀ O'Bʀɪᴇɴ Хм, я посмотрю ... также есть ли команда if, которую я jmissed, просматривая документацию / источник, или это единственный вариант? с неуместным третьим аргументом?
набухает
?является ближайшим к если есть в Джольфе. Это как троичный, если. ?ABCs returns B`, если a верно, а Cиначе.
Конор О'Брайен,
2

JavaScript (ES6), 110 байт

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

Работает, нарезая все более длинные части из середины, aпока они не совпадут с двумя концами b. Цикл не является бесконечным, поскольку он остановится на или перед i == a.length.

Нил
источник