Ваша задача - решить проблему SLCSC, которая заключается в поиске кратчайшего кода для решения проблемы самой длинной общей подпоследовательности .
Действительное решение проблемы ЛВП для двух или более строк S 1 , ... S п любая строка T максимальной длины, что характеры Т появляются во всех S I , в том же порядке , как и в T .
Обратите внимание , что T не должен быть суб строка из S я .
пример
Строки axbycz
и xaybzc
имеют 8 общих подпоследовательностей длиной 3:
abc abz ayc ayz xbc xbz xyc xyz
Любое из них будет правильным решением проблемы LCS.
подробности
Напишите программу или функцию, которая решает проблему LCS, как описано выше, соблюдая следующие правила:
Ввод будет состоять из двух или более строк, содержащих только строчные буквы.
Вы можете читать эти строки как массив строк или одну строку с разделителем по вашему выбору.
Ваш код должен выводить одно из возможных решений проблемы, за которым может следовать перевод строки или заключенные в кавычки.
Вы можете предположить, что строки короче, чем 1000 символов, и не более 20 строк.
В этих пределах ваш код должен работать как положено в теории (учитывая неограниченное время и память).
Ваш код должен выполнить объединенные тестовые примеры из следующего раздела менее чем за час на моем компьютере (Intel Core i7-3770, 16 ГБ ОЗУ).
Подходы, которые просто повторяют все возможные подпоследовательности, не будут соответствовать ограничению по времени.
Использование встроенных модулей, которые упрощают эту задачу, например
LongestCommonSequence
, не допускается.
Применяются стандартные правила игры в гольф .
Контрольные примеры
a
ab
Выход: a
aaaaxbbbb
bbbbxcccc
ccccxaaaa
Выход: x
hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl
Вывод: hxbbpyhogntqppcqgkxchpsieuhbncvpuqndbjqmclchqyfttdvgoysuhrrl
или любая другая общая подпоследовательность той же длины
riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg
Вывод: icsvllvjnlktywuar
или любая другая общая подпоследовательность той же длины
rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr
Вывод: krkk
или любая другая общая подпоследовательность той же длины
bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja
Вывод: code
или любая другая общая подпоследовательность той же длины
nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt
Вывод: golf
или любая другая общая подпоследовательность той же длины
epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp
Вывод: пустая строка
источник
Ответы:
CJam, 31
Попробуйте онлайн
9 байтов в гольф благодаря Деннису!
Объяснение:
Этот алгоритм пробует все возможные символы для первой позиции подпоследовательности, заменяет каждую строку подстрокой после первого появления этого символа, а затем вызывает себя рекурсивно (с запоминанием).
источник
Питон -
665644Уровни отступов:
Код определяет функцию
o
, которая принимает список строк в качестве аргументов и возвращает один из LCS для строк.Тестовый код:
Время, необходимое для запуска тестов на моем компьютере:
источник
(n+1)
, вы можете заменить его,-~n
чтобы сохранить 2 байта в каждом случае. Кроме того, везде, где вы используетеmap
сlambda
, рассмотрите возможность использования списка понимания вместо. Например,map(lambda x:x-1,z)
можно сократить на три байта, изменив его на[~-x for x in z]
.r,x=r+(j+1)*x,x*(l[k]+1)
можно сократить доr+=(j+1)*x;x*=(l[k]+1)
. Кроме того, вам не нужно,u=...
потому чтоu
используется только в одном месте. Просто замените этот код на буквуu
.Pyth,
59585535 байтСократите колоссальные 20 байтов благодаря @isaacg!
55-байтовая версия:
Отрежьте 3 байта, изменив
.U@bZ
на@F
(оператор сгиба).58-байтовая версия:
Отрежьте байт, изменив формат логического условия.
59-байтовая версия:
Это было сложно! Python держал сегфолтинг! Я уверен, что это была какая-то ошибка, но я не смог получить минимальный тестовый пример. Ну что ж.
Я основал алгоритм на этом . Что хорошо, за исключением того, что этот предназначен только для двух строк. Мне пришлось немного подправить его, чтобы он работал больше. Затем последний контрольный пример занял слишком много времени, поэтому мне пришлось добавить дополнительную проверку для выхода из рекурсии, если больше нет общих символов.
Это довольно медленно, но должно занять меньше часа (надеюсь). Я тестирую на своем Core i3 с 6 ГБ ОЗУ, так что ваш 16-ГБ Core i7 должен пройти через это. :)
Я также воспользовался функциями автоматического запоминания Pyth, чтобы сделать его немного быстрее.
РЕДАКТИРОВАТЬ : @ Денис сказал, что это проходит!
Чтобы проверить это, добавьте следующую строку:
и дать ему список строк через стандартный ввод (например
['a', 'ab']
).Пояснение к 35-байтовой версии:
WIP.
Пояснение к 55-байтовой версии:
источник
C
618564 байтаИ здесь это распутывается, для «читабельности»:
Дамы и господа, я совершил ужасную ошибку. Он используется , чтобы быть красивее ... А гото-менее ... По крайней мере , сейчас это быстро .
Мы определяем рекурсивную функцию,
L
которая принимает в качестве входных данных массивs
массивов символов и количествоn
строк. Функция выводит результирующую строку в stdout и случайно возвращает размер в символах этой строки.Подход
Хотя код запутан, стратегия здесь не слишком сложна. Мы начнем с довольно наивного рекурсивного алгоритма, который я опишу с помощью псевдокода:
Теперь этот алгоритм сам по себе довольно ужасен (но, как я обнаружил, он может уместиться в ~ 230 байтов). Это не то, как можно получить быстрые результаты. Этот алгоритм невероятно плохо масштабируется с длиной строки. Этот алгоритм делает , однако, масштаб довольно хорошо с большим числом строк. Последний контрольный пример будет решен практически мгновенно, поскольку ни одна строка не
s
имеетc
общих символов . Я реализовал два основных трюка, которые привели к невероятному увеличению скорости:При каждом вызове
L
проверяйте, получали ли мы такой же ввод раньше. Поскольку на практике информация передается через указатели на один и тот же набор строк, нам на самом деле не нужно сравнивать строки, а просто места, и это здорово. Если мы обнаружим, что мы получили эту информацию раньше, нет необходимости выполнять расчеты (большую часть времени, но получение результатов делает это немного более сложным), и мы можем избежать простого возврата длины. Если мы не найдем соответствия, сохраните этот набор ввода / вывода для сравнения с будущими вызовами. В коде C второйfor
цикл пытается найти совпадения с входом. Известные входные указатели сохраняютсяR
, а соответствующие значения длины и вывода символов сохраняются вA
, Этот план оказал сильное влияние на время выполнения, особенно с более длинными строками.Каждый раз, когда мы находим местоположения
c
вs
, есть шанс, что мы сразу узнаем, что то, что мы нашли, не является оптимальным. Если каждое местоположениеc
появляется после некоторого известного местоположения другой буквы, мы автоматически знаем, что этоc
не приводит к оптимальной подстроке, потому что вы можете поместить в нее еще одну букву. Это означает, что за небольшую плату мы можем удалить несколько сотен вызововL
для больших строк. В приведенном выше коде Cy
установлен флаг, если мы автоматически знаем, что этот символ приводит к неоптимальной строке, иz
установлен флаг, если мы находим символ, который имеет только более ранние появления, чем любой другой известный символ. Текущие ранние появления символов хранятся вx
, Нынешняя реализация этой идеи немного грязная, но во многих случаях производительность почти удвоилась.С этими двумя идеями, что не закончилось через час, теперь заняло около 0,015 секунд.
Вероятно, есть еще много маленьких трюков, которые могут ускорить работу, но в этот момент я начал беспокоиться о своей способности играть в гольф все. Я до сих пор не доволен игрой в гольф, поэтому, скорее всего, вернусь к этому позже!
Задержки
Вот некоторый тестовый код, который я предлагаю вам попробовать онлайн :
Я запускал тестовые наборы OP на ноутбуке, оснащенном 1,7-ГГц чипом Intel Core i7 с настройкой оптимизации
-Ofast
. Моделирование сообщило, что требуется пик в 712 КБ. Вот пример выполнения каждого тестового примера с таймингами:В гольфе я значительно улучшил производительность, и, поскольку людям, похоже, понравилась грубая скорость (0,013624 с для завершения всех тестовых случаев вместе) моего предыдущего 618-байтового решения, я оставлю это здесь для справки:
Сам алгоритм не изменился, но новый код опирается на деления и некоторые хитрые побитовые операции, которые в итоге замедляют процесс.
источник
best_found
? Он упоминается только дважды, один раз, когда он используется в условном выражении, и другой, когда он сбрасывается.best_found
он установлен вbest_length + current_depth
. Вероятно, вы должны упомянуть это в объяснении!best_found
- это глобальное целое число, которое описывает длину самой длинной общей подстроки, найденной в любой заданной точке выполнения. Я добавлю это в объяснение!Python 2, 285
Код:
Использование:
Объяснение:
Это рекурсивная функция.
s
это персонаж, которого мы ищем.a
содержит список строк, нарезанных послеs
.b
содержит список строк, которые еще не были затронутыf
возвращает самую длинную общую строку.Первое условие проверяет, закончили ли мы все строки. если это так, это означает, что
s
это общий символ, и он возвращаетs
и ищет более общие символы.Второе условие проверяет, не начинаем ли мы проходить какую-либо строку, то есть у нас даже нет символа (
a==[]
эквивалентноs==''
). если это так, мы проверяем каждый символ первой строки вb
.Последняя строка перемещает первую строку в
b
кa
, находя каждое вхождениеs
в этой строке.При первом вызове
s
должна быть пустая строка.a
должен быть пустой список иb
должен содержать все строки.источник
f(b,s='',a=[])
.