В этой задаче ваша задача - найти подстроки с заданной структурой.
вход
Ваш ввод должен состоять из двух непустых буквенно-цифровых строк, шаблона p
и текста t
. Идея состоит в том, что каждый символ p
представляет собой непрерывную непустую подстроку, t
которая находится рядом друг с другом, и p
представляет их конкатенацию. Одинаковые символы соответствуют одинаковым подстрокам; например, шаблон aa
представляет собой любой непустой квадрат (строка, полученная путем конкатенации более короткой строки к себе). Таким образом, шаблон aa
может соответствовать подстроке byebye
, с каждым a
соответствием bye
.
Выход
Если текст t
содержит подстроку, которая p
соответствует, то ваша продукция должна быть этой подстрокой с двоеточиями, :
вставленными между строками, которые соответствуют символам p
. Например, если у нас есть t = byebyenow
и p = aa
, то bye:bye
это приемлемый вывод. Может быть несколько вариантов для соответствующей подстроки, но вы должны вывести только один из них.
Если t
не содержит подходящей подстроки, ваш вывод должен быть грустным лицом :(
.
Правила и разъяснения
Разные символы p
могут соответствовать одинаковым подстрокам, поэтому p = aba
могут соответствовать строке AAA
. Обратите внимание, что символы должны соответствовать непустым строкам; в частности, если p
оно длиннее t
, вывод должен быть :(
.
Вы можете написать полную программу или функцию, а также изменить порядок двух входов. Побеждает меньшее количество байтов, и стандартные лазейки запрещены.
Тестовые случаи
Дано в формате pattern text -> output
. Обратите внимание, что могут существовать другие приемлемые результаты.
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
источник
O(2^((n * (n + 1))/2))
: PОтветы:
Python, 207 байт
Позвонить с
g(pattern, string)
Использует
re
модуль для выполнения большей части работы.источник
JavaScript (SpiderMonkey) (ES5.1), 198 байт
С тех пор, как ES6 был выпущен в июне 2015 года, я публикую версию кода ES5.1 вместе с эквивалентом ES6, но объявляю версию ES5.1 основным ответом.
Жадное совпадение, поэтому в первом случае возвращается «Не» вместо «N».
Попробуйте онлайн!
JavaScript (Node.js) (ES6), 141 байт
Попробуйте онлайн!
Принимает аргументы в карри синтаксисе:
f(a)(b)
Объяснение (и не разгул):
источник
Брахилог , 35 байт
Попробуйте онлайн!
На не совсем маленьких входах очень медленно. Я на самом деле не делал шестой тестовый случай, но не из-за отсутствия попыток медленного. (Возможно, из-за грубого форсирования каждого раздела каждой подстроки, начиная с самой большой, а затем проверяя, совпадает ли она.) Принимает входные данные в виде списка
[pattern,string]
.Сокращенное и разделенное объяснение:
sᵗ~cᵗX
X - это шаблон в паре с разделом подстроки входной строки.
lᵛ
Узор и раздел имеют одинаковое количество элементов.
Xzdz≠ʰ
Никакие две уникальные
pattern char, matched substring
пары не имеют шаблонного символа. Таким образом, ни один символ шаблона не отображается на несколько подстрок, хотя несколько символов шаблона могут отображаться на одну подстроку.Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("
Вывод - это элементы раздела, объединенные двоеточиями, если что-то не может быть сделано, в этом случае
:(
вместо этого.Монолитное объяснение:
источник