--->
45 задач
<---
Источники
Дана строка S, состоящая из N символов. Определим функцию A(i) от первых i символов этой сроки следующим образом:
A(i) = максимально возможному k, что равны следующие строки:
S[1]+S[2]+S[3]+…+S[k]
S[i]+S[i–1]+S[i–2]+…+S[i–k+1]
где S[i] – i-ый символ строки S, а знак + означает, что символы записываются в строчку непосредственно друг за другом.
Напишите программу, которая вычислит значения функции A для заданной строчки для всех возможных значений i от 1 до N.
В первой строке входного файла записано одно число N. 1≤N≤200000. Во второй строке записана строка длиной N символов, состоящая только из больших и/или маленьких латинских букв.
В выходной файл выведите N чисел — значения функции A(1), A(2), … A(N).
5 aabaa
1 2 0 1 5
В теории кодирования часто используют беспрефиксные коды наборы слов, ни одно из которых не является префиксом (Слово α называется префиксом слова β, если α получается из β удалением нуля или более символов в конце. Например, слова, 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 символов. Суммарная длина всех слов не превышает 106. Все слова различны.
На первой строке выходного файла выведите одно число m - максимальное количество слов, которые можно выбрать из заданного набора, чтобы они образовывали почти беспрефиксный код уровня k. Следующие m строк должны содержать выбранные слова.
6 2 aba bacaba abacaba baca abac caba
3 aba baca caba
Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки.
Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.
Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n — количество повторений символа (целое число от 2 до 99), а A — заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.
В выходной файл выведите восстановленную строку. При этом строка должна быть разбита на строчки длиной ровно по 40 символов (за исключением последней, которая может содержать меньше 40 символов).
ABC
ABC
O2A3O2AO
OAAOOOAAO
A2B3C4D5E6F7G
ABBCCCDDDDEEEEEFFFFFFGGGGGGG
Дана непустая строка S, длина которой N не превышает 106. Будем считать, что элементы строки нумеруются от 1 до N.
Для каждой позиции i символа в строке нас будет интересовать подстрока, заканчивающаяся в этой позиции, и совпадающая с некоторым началом всей строки. Вообще говоря, таких подстрок будет несколько, не меньше двух. Самая длинная из них имеет длину i, она нас интересовать не будет. А будет нас интересовать самая длинная из остальных таких подстрок (заметим, что такая подстрока всегда существует — в крайнем случае, если ничего больше не найдется, сгодится пустая подстрока).
Значением префикс-функции π[i] будем считать длину этой подстроки.
Префикс-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск образца в тексте»).
Требуется для всех i от 1 до N вычислить π[i].
Одна строка длины N, 0 < N ≤ 106, состоящая из маленьких латинских букв.
Выведите N чисел — значения префикс-функции для каждой позиции, разделенные пробелом.
abracadabra
0 0 0 1 0 1 0 1 2 3 4
Дана непустая строка s, длина которой N не превышает 106. Будем считать, что элементы строки нумеруются от 1 до N.
Для каждой позиции i символа в строке определим Z-блок как наибольшую подстроку, которая начинается в этой позиции и совпадает с некоторым началом всей строки s. Значением Z-функции Z(i) будем считать длину этого Z-блока. (Заметим, что для первой позиции строки Z-блок совпадает со всей строкой, поэтому Z(1)=N. С другой стороны, если s[i]≠s[1], то Z(i)=0).
Z-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск по образцу»).
Требуется для всех i от 1 до N вычислить Z(i).
Одна строка длины N, 0 < N ≤ 106, состоящая из маленьких латинских букв.
N чисел, разделенные пробелами: Z(1), Z(2), ... Z(N)
abracadabra
11 0 0 1 0 1 0 4 0 0 1