Создайте программу или функцию, которая принимает список строк в качестве входных данных и выводит самую длинную строку, которая является подстрокой всех входных строк. Если имеется несколько подстрок одинаковой длины и больше нет подстроки, выведите любую из них.
- Это может означать вывод пустой строки.
- Если имеется несколько допустимых выходов, вы можете вывести любой из них. Вы не обязаны давать согласованный вывод для данного ввода, если вывод всегда действителен.
- На входе всегда будет хотя бы одна строка, но может не быть непустой строки.
- Все печатные символы ASCII могут появляться на входе. Вы можете предположить, что это единственные символы, которые появляются.
- Вы можете получить ввод или произвести вывод любым из методов по умолчанию .
- Стандартные лазейки не допускаются.
- Это код-гольф - чем меньше байтов кода, тем лучше.
Тестовые случаи:
[Inputs] -> [Valid outputs (choose one)]
["hello", "'ello"] -> ["ello"]
["very", "much", "different"] -> [""]
["empty", "", "STRING"] -> [""]
["identical", "identical"] -> ["identical"]
["string", "stRIng"] -> ["st", "ng"]
["this one", "is a substring of this one"] -> ["this one"]
["just one"] -> ["just one"]
["", "", ""] -> [""]
["many outputs", "stuptuo ynam"] -> ["m", "a", "n", "y", " ", "o", "u", "t", "p", "s"]
["many inputs", "any inputs", "ny iii", "yanny"] -> ["ny"]
["%%not&", "ju&#st", "[&]alpha_numeric"] -> ["&"]
code-golf
string
subsequence
Сара Дж
источник
источник
undefined
означает, что нет допустимой выходной строки. Если пустая строка (или любая другая строка) является допустимым выводом, утверждение о том, что допустимого вывода нет, неверно.Ответы:
Python 2 , 82 байта
Попробуйте онлайн!
Принимает входные данные Время ожидания для входов, где первая строка длинная.
Идея состоит в том, чтобы взять подстроки первых строк,
h
чтобы найти самую длинную, которая появляется во всех оставшихся строкахt
. Для этого мы рекурсивно разветвляемся на удаление первого или последнего символаh
.Python 2 , 94 байта
Попробуйте онлайн!
Более прямой метод. Вспомогательная функция
g
генерирует множество всех подстрокs
, а основная функция берет самую длинную в их пересечении.источник
Brachylog (v2),
39 байтПопробуйте онлайн!
Полная программа. Ввод из стандартного ввода (в виде списка строк в стиле JSON), вывод в стандартный вывод.
объяснение
По-видимому, порядок разрыва связей
s
не тот, который есть почти во всем остальном в Brachylog, поэтому нам нужно вручную переопределить его, чтобы получить самый длинный вывод. (Это немного расстраивает: четыре дополнительных символа для переопределения, плюс два символа группировки, потому что Brachylog не анализирует два метапредиката подряд.)Brachylog
s
не возвращает пустые подстроки, поэтому нам нужно немного обдумать это: вместо того, чтобы отправлять функцию (что обычно и делается), мы пишем полную программу, выводим ее на стандартный вывод. Таким образом, если есть общая подстрока, мы просто выводим ее, и все готово. Если нет общей подстроки, программа выдает ошибку - но она все равно ничего не печатает на стандартный вывод, таким образом, она выводит пустую строку, как и предполагалосьисточник
s
неправильно, и переопределение порядка разрыва связи довольно дорого в плане байтов. Делая это сейчас, тем не менее, потому что важно, чтобы ответ был правильным. Каким-то образом ни один из тестов, которые я пробовал, не заметил разницы.s
подстрок состоит в том, чтобы сначала дать все префиксы ввода (самый длинный сначала), затем отбросить первый и повторитьЖеле ,
126 байтПопробуйте онлайн!
Спасибо @JonathanAllan за сохранение 6 байтов!
источник
Ẇ€œ&/Ṫḟ0
что сделал бы работу и сохранил четыре байта, поскольку подстроки уже упорядочены по длине, следовательно, отфильтрованный результат будет; тогда остается только то, что при отсутствии совпадений tail выдает ноль, и, поскольку нам гарантированы списки символов, мы можем их просто отфильтровать.œ&/
может быть замененоf/
здесь спасением другогоẆ€f/ṛ/
.Ruby 2.6,
76 5954 байтаПопробуйте онлайн! - Ruby 2.5 версия (56 байт)
Как?
Создайте список возможных совпадений, изначально установив исходный массив. Выполните итерацию по списку, и, если строка не совпадает, добавьте 2 новые строки в конец списка, обрезав первый или последний символ. В конце совпадение (в конце концов пустая строка) будет найдено.
Спасибо Кирилл Л за -2 байта и гистократ за еще -2
источник
R ,
119116108106 байтПопробуйте онлайн!
Найдите все подстроки каждой строки, найдите пересечение каждого списка подстрок, затем, наконец, верните (одну из) самую длинную.
-3 байта благодаря Кириллу Л.
-8 байт, используя
lapply
вместоMap
-2 байта благодаря Кириллу Л. снова, удаляя брекеты
источник
nchar
достаточно, чтобы что-то сохранить, объявивnchar
унарным оператором.list
Аналогично, псевдоним дает нам -3 байта.05AB1E ,
1498 байтов-6 байт благодаря @Adnan .
Попробуйте онлайн или проверьте все тесты .
Объяснение:
источник
€Œ.«Ãõªéθ
должно работать на 9 байтов.Å«Ã
, но не понял, что я должен был бы использовать.«Ã
вместо .. Спасибо!€Œ.«ÃéθJ
должно работать на 8.Zsh ,
126 ...96 байт-3 байта для арифметики для, -6 байтов для неявного
"$@"
(спасибо roblogic), -5 байтов для удаления ненужных{
}
, -1 байт для краткой формыfor
, -1 байт для использованияrepeat
, -1 байт для объединенияfor s ($b)
с его телом, -13 байт изменив повторяющуюся петлю для некоторого рывка.Попробуйте онлайн! Попробуйте онлайн!Попробуйте онлайн!Мы читаем все возможные подстроки в массив
a
, а затем устанавливаемb
пересечение массивовa
иb
. Конструкция${b-$a}
будет заменять только$a
на первой итерации: в отличие от расширения одного уровня${b:-$a}
, она не будет заменять, когдаb
она установлена, но пуста.источник
a+=( $l[1+i/$#l,1+i%$#l] )
for
цикловfor l in "$@"
простоfor l;
- это обман трюкаb=(${${b-$a}:*a})}
man zshexpn
иman zshparam
особенно. Они всегда открыты при написании ответа.Haskell , 80 байт
Попробуйте онлайн!
Получить все суффиксы (
tails
) первого словаx
в списке и принять все префиксы (inits
) из этих суффиксов , чтобы получить все подстрокиs
изx
. Сохраните каждую изs
этихisInfixOf
all
строк в оставшемся спискеr
. Сортировать эти подстроки по длине ( с использованием в(0<$)
трик ) и вернуть последний.источник
Сетчатка 0.8.2 , 48 байт
Попробуйте онлайн! Объяснение:
Для каждого суффикса первой строки найдите самый длинный префикс, который также является подстрокой всех других строк. Перечислите все эти суффиксные префиксы (то есть подстроки). Если нет подходящих подстрок, мы просто получим пустую строку, что нам и нужно.
Сортируйте подстроки в обратном порядке длины.
Оставьте только первую, то есть самую длинную подстроку.
источник
n
- количество строк аргумента. Тогда(?=(.*\n.*\1)*.*$)
должно быть(?=(.*\n.*\1){n-1}.*$)
, не так ли? Прецедент:["very", "different", "much"] -> [""]
{n}
вы можете удалить шаблоны начала и конца и сохранить ,(.+)(?=(.*\n.*\1){n}
если Retina позволяет писатьn
короче(?<=^.*).*$
TSQL-запрос, 154 байта
Попробуйте онлайн
Делается чувствительным к регистру, объявляя столбец «a» с сопоставлением, содержащим CS (с учетом регистра)
Разбивая все строки из 2540 начальных позиций (многие идентичны), но полезные значения варьируются от 1 до 2070 и заканчивая от 0 до 22 символов после начальной позиции, конечная позиция может быть длиннее, если изменить тип на «P» вместо «L», но повредит производительность.
Эти отдельные строки в каждом ряду подсчитываются. Максимальное количество всегда будет равно количеству строк в табличной переменной '@'. Изменение порядка на том же счетчике приведет к тому, что подстрока с большинством совпадений останется в верхней части результатов, после чего обратная длина подстроки оставит самое длинное совпадение с большинством совпадений сверху. В запросе только выберите 1 верхнюю строку.
Чтобы получить ответы на все вопросы, измените первую часть запроса на
источник
C # (интерактивный компилятор Visual C #),
320257 байтПопробуйте онлайн!
Реквизит для @Expired Data и @dana
источник
Perl 6 ,
6260 байтПопробуйте онлайн!
Я немного раздражал Perl 6 не может сделать набор операций над списками списков, поэтому есть дополнительный
.comb
и>>
там.Еще одна досадная вещь - это то, что яКак указано в комментариях,max
не могу взять функцию для сравнения предметов, то естьsort
вместо этого я должен использовать .max
может принимать аргумент, однако он заканчивается дольше, так как мне приходится учитыватьmax
возврат отрицательной бесконечности, когда есть общие подстроки ( попробуйте онлайн! ).источник
max
может принимать такую функцию (хотя arity 1) либо по положению при вызове в режиме OO, либо поименованному:by
аргументу в процедурном режиме.Japt v2.0a0
-hF
, 8 байтСпасибо Shaggy за сохранение 3 байта
Попытайся
источник
-F
умолчанию используется пустая строка.Japt
-h
, 8 байт(Я мог бы сбросить последние 3 байта и использовать
-Fh
вместо этого флаг, но я не фанат использования-F
)Попробуйте или запустите все тесты
источник
Python 3 , 137 байт
Попробуйте онлайн!
источник
Python 2 , 103 байта
Попробуйте онлайн!
Это анонимная лямбда, которая преобразует каждый элемент во множество всех подстрок, затем
reduce
устанавливает его через set intersection (set.__and__
), а затем возвращаетmax
элемент черезlen
gth.источник
set.intersection
.C # (интерактивный компилятор Visual C #) ,
147145 байтПопробуйте онлайн!
источник
Perl 5 (
-aln0777F/\n/
-M5.01
-MList::util=max
), 99 байтможет быть в гольф более определенно
TIO
источник
JavaScript (ES6),
9892 байтаПопробуйте онлайн!
источник
Древесный уголь , 30 байт
Попробуйте онлайн! Ссылка на подробную версию кода. Этот алгоритм более эффективен и короче, чем генерация всех подстрок. Объяснение:
Вставьте последнюю строку из списка ввода в переменную.
Обнулить начальный индекс подстроки.
Обведите все возможные индексы конца подстроки. (На самом деле это цикл с 0, исключая длину, поэтому значение корректируется позже.)
Получить текущую подстроку.
Проверьте, содержится ли эта подстрока во всех других входных строках.
Если это так, то замените любую ранее выведенную подстроку
В противном случае попробуйте увеличить начальный индекс подстроки.
источник
Баш ,
295.. 175 байтНе красиво, но, по крайней мере, это работает. Попробуйте онлайн
-37 путем генеральной уборки ; -52 путем плагиата из zsh ответа ; -26 путем замены массива на цикл ; -2 благодаря GammaFunction ; -3 снято
i=0
сfor
петлиВот оригинальный скрипт без комментариев с комментариями
источник
((k==$#))&&
на((k-$#))||
. Это также позволяет вам использоватьk=
вместо установки его на 0.Красный ,
266174 байтаПопробуйте онлайн!
Изменил рекурсию на итерацию и избавился от сортировки.
источник
Perl 5 , 87 байт
Попробуйте онлайн!
источник
JavaScript (Node.js) , 106 байт
Попробуйте онлайн!
источник
Gaia , 15 байт
Попробуйте онлайн!
источник
PowerShell ,
16516387 байт-76 байт благодаря Nail для удивительного регулярного выражения .
Попробуйте онлайн!
Менее гольф:
источник
JavaScript (Node.js) , 90 байт
Попробуйте онлайн! Тестовые случаи бесстыдно украдены у @Arnauld. Порт моего древесного угля ответ.
источник
Java (JDK) , 158 байт
Попробуйте онлайн!
кредиты
источник
Perl 5 , 86 байт
Попробуйте онлайн!
источник
Pyth , 16 байт
Попробуйте онлайн!
источник