Вступление
В этой задаче ваша задача - найти обобщенные подпоследовательности строк. Подпоследовательности не обязательно являются смежными, и они также могут «обвивать» строку, проходя через ее конец и начиная снова с начала. Вы хотите минимизировать количество оберток, хотя.
Более формально, пусть u
и v
будут любые две строки и k ≥ 0
целое число. Мы говорим , что u
это k
-упаковочная и дозирующая подпоследовательность из v
, если существует различные показатели , такие , что и в большинстве индексов удовлетворяют . Это означает, что его можно найти внутри , перейдя слева направо, выбрав некоторые из его символов в пути и обернувшись вокруг в большинстве случаев (эквивалентно, выполняя самое большее размах ). Обратите внимание, что ни один символ не может быть выбран более одного раза, даже после переноса , и что подпоследовательности обтекания - это в точности обычные подпоследовательности, с которыми мы все знакомы.i1, i2, ..., ilen(u)
u == v[i1] v[i2] ... v[ilen(u)]
k
ij
ij > ij+1
u
v
k
k+1
v
0
Задание
Ваши входные данные представляют собой две непустые буквенно-цифровые строки u
и v
, а ваши выходные данные представляют собой наименьшее целое число k
, которое u
является k
подпоследовательностью -wrapping v
. Если такого не k
существует, вывод должен быть -1
.
пример
Рассмотрим входы u := xyzyxzzxyx
и v := yxzzazzyxxxyz
. Если мы начнем искать персонажей u
в v
жадной манере, мы обернемся 3 раза:
yxzzazzyxxxyz
>─x─────y────z┐
┌─────────────┘
└y───────x────┐
┌─────────────┘
└──zz─────x─y─┐
┌─────────────┘
└──────────x──>
Таким образом, правильный вывод - максимум 3. Обратите внимание, как крайний левый символ x
выбирается один раз, а затем игнорируется во втором цикле, поскольку его нельзя использовать повторно. Тем не менее, существует более короткий метод только с двумя переходами:
yxzzazzyxxxyz
>──────────xyz┐
┌─────────────┘
└yxzz────x────┐
┌─────────────┘
└───────y─x───>
Оказывается, одного обхода (то есть двух циклов) недостаточно, поэтому правильный вывод получен 2
.
Правила и бонусы
Вы можете написать либо функцию, либо полную программу, а также при необходимости изменить порядок входных данных. Побеждает меньшее количество байтов, и стандартные лазейки запрещены.
Существует бонус -10% для вычисления всех тестовых случаев менее чем за 10 секунд. Я буду проверять неясные случаи на моей машине; моя эталонная реализация в Python занимает около 0,6 секунд. У меня есть 7-летний ноутбук с двухъядерным процессором 1,86 ГГц, который вы можете принять во внимание.
Тестовые случаи
"me" "moe" -> 0
"meet" "metro" -> -1
"ababa" "abaab" -> 1
"abaab" "baabaa" -> 1
"1c1C1C2B" "1111CCCcB2" -> 3
"reverse" "reserved" -> 2
"abcdefg" "gfedcba" -> 6
"xyzyxzzxyx" "yxzzazzyxxxyz" -> 2
"aasdffdaasdf" "asdfddasdfsdaafsds" -> 2
источник
x
используется в трех различных циклах. Он может быть использован только один раз.Ответы:
Pyth, 34 байта
Это определяет функцию
g
, которая принимает две строки в качестве параметра. Попробуйте онлайн: Pyth Compiler / ExecutorЭтот код очень неэффективен. Это имеет время и сложность памяти
len(v)!/(len(v)-len(u))!
. Он не может решить более длинные тестовые случаи менее чем за 10 секунд. (Это также может произойти сбой, так как не хватит памяти.)источник
Haskell, 160 * 0,9 = 144 байта
Время для всех тестовых случаев (примечание: аргументы перевернуты):
Как это работает (короткая версия): простая грубая сила, которая требует минимум использования соответствующего символа и пропускает его. Я прекращаю поиск по окончании (возвращая количество циклов) или когда количество циклов больше, чем минимальное (возвращая -1).
По сравнению с моей первой версией сэкономлено много байтов, в основном потому, что я перешел с полной программы на функцию.
С некоторыми комментариями и надлежащим интервалом в гольф Haskell вполне читабелен:
Для справки: старая версия, полная программа, 187 байт
источник
JavaScript (ES6) 174 (193 - 10%)
Рекурсивный поиск, как и ответ @ nimi, сохраняющий минимум оберток. Пространство решений велико (прежде всего, в последнем примере), но сокращение поиска до минимума, найденного в данный момент, сокращает время. Редактировать 1 Добавить отсутствующий тестовый пример, немного укороченный Редактировать 2 Нет необходимости передавать параметр w вокруг, это исправлено
Ungolfed
Тест в консоли Firefox / FireBug
Выход (последняя строка - время выполнения в мс)
источник