| Условие задачи | | Прогресс |
Темы:
Z-функция. Префикс-функция
В теории кодирования часто используют беспрефиксные коды наборы слов, ни одно из которых не является префиксом. Слово α называется префиксом слова β, если α получается из β удалением нуля или более символов в конце. Например, слова a, ab и aba являются префиксами слова aba. Например, набор слов aba, aa и bac является беспрефиксным кодом, а набор abac, aba, ba нет, поскольку слово aba является префиксом слова abac.
Профессор Дешифро работает в лаборатории исследования бесполезной информации и изучает свое новое изобретение почти беспрефиксные коды. Набор слов называется почти беспрефиксным кодом уровня k, если наибольший общий префикс двух любых слов из набора не превышает по длине k. Например, набор abac, abс, ba является почти беспрефиксным кодом уровня 2, а набор abac, abab, ba нет, поскольку наибольший общий префикс слов abac и abab имеет длину 3.
Очередная задача, которую профессор Дешифро поставил своим лаборантам, заключается в следующем: по заданному набору слов и числу k требуется выбрать из заданных слов максимальный набор, который является почти беспрефиксным кодом уровня k. Вам, как младшему лаборанту, поручили написать соответствующую программу.
Входные данные
Первая строка входного файла содержит два целых числа: n и k количество слов в заданном наборе и уровень почти беспрефиксного кода, который требуется построить (\(1<= n <= 100000\), \(0 <= k <= 200\)). Следующие n строк содержат по одному слову. Слова состоят из строчных букв латинского алфавита. Длина каждого слова от 1 до 200 символов. Суммарная длина всех слов не превышает \(10^6\). Все слова различны.
Выходные данные
Выведите одно число m - максимальное количество слов, которые можно выбрать из заданного набора, чтобы они образовывали почти беспрефиксный код уровня k.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 2
aba
bacaba
abacaba
baca
abac
caba
|
3 |
| |
![]()
|
|
Темы:
Z-функция. Префикс-функция
Дана непустая строка S, длина которой N не превышает \(10^6\). Будем считать, что элементы строки нумеруются от 1 до N.
Для каждой позиции i символа в строке нас будет интересовать подстрока, заканчивающаяся в этой позиции, и совпадающая с некоторым началом всей строки. Вообще говоря, таких подстрок будет несколько, не меньше двух. Самая длинная из них имеет длину i, она нас интересовать не будет. А будет нас интересовать самая длинная из остальных таких подстрок (заметим, что такая подстрока всегда существует — в крайнем случае, если ничего больше не найдется, сгодится пустая подстрока).
Значением префикс-функции \(\pi[i]\) будем считать длину этой подстроки.
Префикс-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск образца в тексте»).
Требуется для всех i от 1 до N вычислить \(\pi[i]\).
Входные данные
Одна строка длины N, \(0 < N <= 10^6\), состоящая из маленьких латинских букв.
Выходные данные
Выведите N чисел — значения префикс-функции для каждой позиции, разделенные пробелом.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
abracadabra |
0 0 0 1 0 1 0 1 2 3 4 |
| |
![]()
|
|
Темы:
Z-функция. Префикс-функция
Арсений — молодой перспективный спортсмен. Всё, что любит делать Арсений — это тренироваться и вкусно есть. Также он отличается пунктуальностью. Только что он составил расписание из n пунктов: для каждого из следующих n часов он решил, что будет делать в это время — тренироваться или есть.
Арсений показал расписание своему тренеру, но ему оно не до конца понравилось. Тренер объяснил, что тренироваться в следующий час после приёма пищи вредно для здоровья.
Теперь Арсений хочет изменить свое расписание так, чтобы он ни разу не тренировался непосредственно после еды. При этом он хочет изменить минимальное число пунктов своего расписания. Помогите Арсению!
Входные данные
В первой строке входных данных содержится число n — количество пунктов в расписании Арсения ( 1 ≤ n ≤ 105 ).
Во второй строке содержится исходное расписание Арсения. Это строка s длины n , состоящая только из латинских букв « t » и « e », при этом если на позиции i в строке s стоит буква « t », то это значит, что в i -м часу Арсений запланировал тренироваться, а если на этой позиции стоит буква « e », то это значит, что в i -м часу Арсений запланировал есть.
Выходные данные
В первой строке выведите минимальное количество пунктов расписания, которые необходимо изменить.
Во второй строке выведите строку из n латинских букв « t » и « e » — изменённое расписание в том же формате, что и во входных данных. Если подходящих расписаний несколько, выведите любое из них.
| № |
Входные данные |
Выходные данные |
| 1 |
6
tttete |
1
ttteee |
| 2 |
5
tttte |
0
tttte |
| 3 |
9
eeeeetttt |
4
eeeeeeeee |
| |
![]()
|
|
Темы:
Z-функция. Префикс-функция
Рома и Денис отправились на соревнование по программированию. В долгой дороге ребята вспоминали операции над строками. Денис сказал, что в Python строки можно умножать на число, тогда Рома, программирующий на С++, решил придумать операцию перемножения строк. По версии Ромы, умножение строки s длины n на строку t обозначается как s·t и равно строке t+s1+t+s2+...+t+sn+t, где si обозначает i-й символ строки s, а знаком « + » обозначено сложение (конкатенация) строк. Например, произведением строк « abc » и « de » является строка « deadebdecde », а произведением строк « z » и « ab » является строка « abzab ». Обратите внимание, что, в отличие от умножения чисел, произведение строк s и t, вообще говоря, не равно произведению строк t и s.
Денис решил продолжить мысль Ромы — он, как ценитель прекрасного, решил определить красоту строки как максимальную длину подряд идущей группы одинаковых букв. Например, красота строки « xayyaaabca » равна 3, так как самая длинная группа подряд идущих одинаковых букв — это « aaa », а красота строки « qwerqwer » равна 1, потому что все соседние буквы в ней различны.
Чтобы развлечь Дениса, Рома написал ему на листочке n строк p1,p2, p3, ... ,pn и попросил его вычислить красоту строки (...((p1·p2)·p3)·...)pn. Денис не до конца понял, как работает умножение Ромы, но не хочет признаваться в этом, поэтому просит посчитать красоту этой строки вас. Рома знает, что Денис слишком впечатлительный, поэтому гарантирует, что красота полученной строки не превосходит 109.
Входные данные
В первой строке содержится число n (1 ≤ n ≤ 100000) — количество строк, которые написал Рома.
В следующих n строках содержатся непустые строки p1, p2, ..., pn, состоящие из маленьких букв английского алфавита.
Гарантируется, что суммарная длина строк не превосходит 100000, а также, что красота произведения всех строк не превосходит 109.
Выходные данные
Выведите одно целое число — красоту произведения строк.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
3
a
b
a |
3 |
произведение трёх строк равно « abaaaba » |
| 2 |
2
bnn
a |
1 |
произведение двух строк равно « abanana » |
| |
![]()
|
|
Темы:
Z-функция. Префикс-функция
Сегодня на уроке Петя узнал про беспрефиксные коды. Множество строк называется беспрефиксным кодом, если
- Все строки в множестве различны
- Не существует такой пары различных строк, что одна строка является префиксом другой
Строка s называется префиксом строки t, если длина строки s не больше длины t, а также для любого i, i-й символ строки s совпадает с i-м символом строки t. Например, ab является префиксом ab и abc, но не является префиксом a и ac.
Петя же решил придумать что-то новое и ввел новое понятие — k-беспрефиксный код. Таким кодом он назвал множество строк, такое, что:
- Все строки в множестве различны
- У любых двух различных строк наибольший общий префикс имеет длину не больше k
Наибольшим общим префиксом двух строк s и t называется наибольшая по длине строка, являющаяся префиксом обеих строк.
Теперь по данному множеству строк s1, s2, ..., sn и числу k Петя хочет найти в этом множестве k-беспрефиксный код, состоящий из максимально возможного количества строк. Помогите ему — найдите этот код.
Входные данные
В первой строке содержится два числа n и k — количество строк в множестве и максимальная длина общего префикса соответственно (1 ≤ n ≤ 105, 1 ≤ k ≤ 100).
В i-й из следующих n строк содержится строка из строчных латинских букв si — i-е слово из множества (1 ≤ |si| ≤ 100).
Гарантируется, что суммарная длина всех строк в множестве не превосходит 106.
Выходные данные
В первой строке выведите число m - максимально возможное количество строк в k-беспрефиксном
коде. В i-й из следующих m строк выведите i-й элемент этого кода. Элементы кода можно выводить в любом порядке.
Если существует несколько ответов с максимальным m, разрешается вывести любой.
| Ввод |
Вывод |
5 2
aabc
acbd
aac
acba
aab |
3
aab
aac
acba |
4 2
aa
abc
aa
abb |
3
aa
abb
abc |
Замечание
В первом примере у строк 1 и 5, а также у строк 2 и 4 наибольший общий префикс больше k, поэтому максимальное количество строк, из которых может состоять k-беспрефиксный код - 3. Во втором примере у любой пары подстрок наибольший общий префикс не больше 2, однако, так как код не может содержать одинаковые строки, больше 3 строк в него не включить.
| |
![]()
|
|
Темы:
Динамическое программирование
Z-функция. Префикс-функция
Хлоя хочет написать письмо своей подруге. Письмо - строка s, состоящая из строчных латинских букв.
К сожалению, как только Хлоя начала писать письмо, она поняла, что оно слишком длинное, и писать его целиком придётся очень долго. Поэтому она хочет написать сжатую версию строки s вместо самой строки.
Сжатая версия строки s — последовательность строк c1, s1, c2, s2, ..., ck, sk, где ci — десятичная запись числа ai (без лидирующих нулей), а si — некоторая строка из строчных латинских букв. Если Хлоя запишет строку s1 ровно a1 раз, потом s2 ровно a2 раз, и так далее, у нее получится строка s.
Длина сжатой версии равна |c1| + |s1| + |c2| + |s2|... |ck| + |sk|. Среди всех сжатых версий Хлоя хочет выбрать такую, что её длина минимальна. Помогите Хлое определить минимально возможную длину.
Входные данные:
В единственной строке входных данных записана строка s, состоящая из строчных латинских букв (1 ≤ |s| ≤ 5000).
Выходные данные:
Выведите одно целое число — минимальную длину сжатой версии строки s.
Примеры:
| Входные данные |
Выходные данные |
| aaaaaaaaaa |
3 |
| abcab |
6 |
| cczabababab |
7 |
Пояснения:
В первом примере Хлоя выберет следующую версию: c1 — 10, s1 — a.
Во втором примере Хлоя выберет следующую версию: c1 — 1, s1 — abcab.
В третьем примере Хлоя выберет следующую версию: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — ab.
| |
![]()
|
|
Темы:
Z-функция. Префикс-функция
Строки
По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, в кокам пряокде рсапожолены бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бкувы мгоут селдовтаь в плоонм бсепордяке, все-рвано ткест чтаитсея без побрелм. Пичрионй эгото ялвятеся то, что мы чиатем не кдаужю бкуву по отдльенотси, а все солво цликеом.
Вдохновившись исследованием британских учёных о восприятии человеком текста, Вася решил, что современная письменность нуждается в серьёзном упрощении. В частности, в лексиконе Васи все слова состоят только из букв a, b и c. Кроме того, память у Васи плохая, поэтому Вася помнит лишь слова, которые содержат не более L букв.
Более того, с тех пор как наш юный друг пролил кофе на свой любимый ноутбук, он не утруждает себя нажатием клавиши пробел (объясняя это тем, что и отсутствие пробелов в тексте совершенно не мешает его пониманию). Однако остальные клавиши клавиатуры работают исправно, что позволяет Васе набирать все известные ему слова без единой орфографической ошибки.
Британские учёные очень заинтересовались исследованиями Васи. Они вступили с молодым учё- ным в активную переписку, однако, получив очередное Васино сообщение были несколько озадачены тем, что же он имел ввиду. Так как разобраться они так и не смогли, а очередное революционное открытие уже было проанонсировано в СМИ, они решили как-то оценить уровень гениальности автора. Для этого они решили понять, а из какого минимального количества слов может состоять словарный запас Василия?
Формат входных данных
В первой строке входных данных содержится целое число L — максимальная длина слова, кото- рое может содержаться в лексиконе Васи (1 <= L <= 10 000). В следующей строке содержится непустое сообщение, полученное учеными. Длина сообщения не превосходит 20 000 символов.
Формат выходных данных
В первой строке выведите единственное число K — минимальное количество слов, которые дол- жен знать Василий, чтобы написать данное сообщение. В следующих K строках выведите сами сло- ва, каждое из которых должно иметь длину не превосходящую L. В случае, если ответов несколько, разрешается выдать любой из них.
Пример
Ввод:
3
ababaabab
Вывод:
2
aba
ab
Замечание
В первом примере из условия одним из возможных способов проинтерпретировать Васино сооб- щение является: ab aba ab ab.
| |
![]()
|