--->
45 задач
<---
Источники
Вам заданы две строки длиной не более 50000 символов. Назовем строку хорошей, если она удовлетворяет условию, что если дописать ее в конец самой себе достаточно много раз, то в полученной строке будут содержаться в качестве подстрок обе заданные строки. Например, для строк “ababa” и “bab” строка “ab” является хорошей – действительно, дописав ее в конец себе два раза, мы получим строку “ababab”, которая содержит обе заданные строки в качестве подстрок. Для двух заданных строк найдите самую короткую хорошую строку.
Входной файл содержит две заданные строки. Строки состоят из символов с ASCII-кодами от 33 до 127. Длина каждой из них не превышает 50000.
Выведите в выходной файл ответ на задачу. Если существует несколько различных оптимальных хороших строк, то выведите любую.
ababa bab
ab
У Андрюши есть маленькая сестричка Аня. Она любит писать сообщения своему другу Гоше. Она хочет, чтобы никто не мог прочитать ее сообщения, поэтому она шифрует их подстановочным шифром. Подстановочный шифр заменяет каждый символ в сообщении на какой-либо еще, при этом равные символы заменяются на равные, а различные — на различные. Например, при шифровании с помощью подстановочного шифра e – a, l – b, o – w, v - c слово "love" оказывается зашифровано как "bwca".
Андрюша недавно перехватил одно из Аниных сообщений t и хочет выяснить, встречается ли там текст р. А именно, он хочет найти все позиции i, такие что существует подстановочный шифр, такой что t[i..i+|р| — 1] представляет собой зашифрованную версию р. Будем называть такие позиции потенциальными вхождениями р в t. Помогите Андрюше найти все потенциальные вхождения р в i.Первая строка входного файла содержит t. Вторая строка входного файла содержит р. Каждая строка состоит из символов с ASCII кодами от 33 до 126. Длина р не превышает длины t. Длина t не превышает 200 000. Обе строки непусты.
Первая строка выходного файла должна содержать к — количество потенциальных вхождений р в t. Вторая строка должна содержать к целых чисел — позиции потенциальных вхождений. Позиции в строке нумеруются, начиная с 1. Позиции следует перечислить в возрастающем порядке.
За тесты в которых \(t \le 1000\) начисляется 50% баллов. За остальные тесты тоже 50%. Баллы начисляются только при прохождении всех тестов группы.
abacabadabacaba aba
7 1 3 5 7 9 11 13
abacabadabacaba love
0
Цепочкой слов длины n назовем последовательность слов w1, w2, ..., wn такую, что для 1 ≤ i ≤ n слово wi является собственным префиксом слова wi + 1.
Напомним, что слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u.
Задано множество слов S = {s1, s2, ..., sm}. Найдите максимальную длину цепочки слов, которую можно построить, используя (возможно, не все) слова этого множества.
Первая строка входного файла содержит целое число m(1 ≤ m ≤ 255). Каждая из последующих m строк содержит по одному слову из множества S.
Все слова не пусты, имеют длину, не превосходящую 255 символов, и состоят только из строчных букв латинского алфавита.
В выходной файл выведите ответ на задачу.
3 a ab abc
3
5 a ab bc bcd add
2
В стандартном поточике вводика или файлике inputik.txt ваша программочка найдёт строчечку из маленьких латинских буковок, которую мы назовём исходненькой. На следующей строчечке программочка найдёт числище N (1 ≤ N ≤ 1 000 000), а в следующих N строчечках — по словечку из тех же маленьких латинских буковок; эти словечки мы назовём словариком. Суммарненькая суммочка длиннищ словечек из словарика не превосходит 1 000 000
Ваша программочка должна вывести на стандартный поточичек выводика или в файлик outputik.txt N строчечек. В i-ой строчечке программочка должна вывести несколько чиселок: первое чиселко - количюсик (сколько штучечек) вхожденьечек строчечки i из словарика в исходненькой, затем через пробельчик для каждого вхожденьичка выведите индексики началиков всех вхожденьичек этой строчечки в исходненькую в отсортированном порядочке. Индексики всех строчечек начинаются с единичек. Няшечки-преподавашечки гарантируют, что колючюсик вхожденьичек не превосходит 1 000 000.
abracadabra
4
abra
ab
marazm
cadabra
2 1 8
2 1 8
0
1 5
Рассмотрим последовательность n целых чисел от 1 до m. Подпоследовательность подряд идущих чисел называется рефреном, если произведение ее длины на количество вхождений в последовательность максимально.
По заданной последовательности требуется найти ее рефрен.
Первая строка входного файла содержит два целых числа: n и m (1 ≤ n ≤ 150 000, 1 ≤ m ≤ 10).
Вторая строка содержит n целых чисел от 1 до m.
Первая строка выходного файла должна содержать произведение длины рефрена на количество ее вхождений. Вторая строка должна содержать длину рефрена. Третья строка должна содержать последовательность которая является рефреном.
9 3 1 2 1 2 1 3 1 2 1
9 3 1 2 1