Задача A. Префикс-функция

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Дана строка s. Найдите сумму значений префикс-функции для всех позиций строки s.

Формат входного файла

Во входном файле записана единственная строка s.

Формат выходного файла

В выходной файл выведите одно число — ответ на задачу.

Ограничения

1 ≤ |s| ≤ 150000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
abcaabacabc
11

Problem B. Knuth-Morris-Pratt

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives two strings and finds position where the second string appears in the first one as a substring.

Input file format

First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a' to 'z' and spaces.

Output file format

Output file must contain a single integer — position of the first occurrence of the substring in a string, or  − 1 if there is none. Positions are numbered from 1.

Constraints

Length of each string does not exceed 100000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
yezhiki nachinayut i vyygryvayut
yut
16

Problem C. Banner scrolling

Author:A. Klenin, I. Tuphanov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Young web developer Vasya was hired by "Dalstolb" company. Company maintains a popular news website with many advertisement banners. Marketing department of "Dalstolb" has proposed a new idea for animated transition between two text messages on the banner.

Message is a single line of characters. First message has length L1, second has length L2 ≥ L1. Since the banner width is only enough to fit L1 characters, the message after the transition should contain any substring the second message of length L1. Transition should be performed as a series of animation frames. Each frame, message is either scrolled to the right by removing leftmost character and appending arbitrary new character from the right, or scrolled to the left by removing rightmost character and appending arbitrary new character from the left.

You program must, given two messages, find a shortest possible transition between them.

Input file format

First line of the input file contains the first message. Second line of the input file contains the second message. Messages are composed of small Latin letters.

Output file format

First line of output file must contain integer N — minimum number of frames. Following N lines must contain two-character string each — frame descriptions. First character must be either L or R, denoting right or left scrolling correspondingly. Second character must be a small Latin letter which should be appended to the message.

Constraints

1 ≤ L1 ≤ L2 ≤ 2000;

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
acm
solutionaccepted
1
Ln
2
vvostoker
vladivostok
4
Rz
Li
Ld
La

Задача D. Нормальная палиндромика

Автор:Жюри летних сборов, И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Палиндром — это строка, которая одинаково читается и в прямом, и в обратном порядке. Например, kazak — палиндром, а kazachka — нет. По данной строке S требуется найти такую кратчайшую (возможно, пустую) строку P, что строка S + P будет палиндромом.

Формат входного файла

Во входном файле содержится строка S, состоящая из маленьких латинских букв.

Формат выходного файла

В выходной файл необходимо вывести строку P.

Ограничения

Длина исходной строки не превосходит 300000 символов.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
abcc
ba
2
abcd
cba

Problem E. Fibonacci level

Author:M. Sporyshev, A. Klenin, A. Baranov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

For arbitrary non-empty strings S1 and S2, the Fibonacci sequence of strings is defined by a recurrence Si + 2 = Si + 1 + Si, where the '+' sign denotes string concatenation.

Let's say that string T has Fibonacci level n if there exists some Fibonacci sequence of strings which contains Sn = T. Note that any string of length 2 or more has Fibonacci level 3.

Your program must, given a string T, find its maximum Fibonacci level n as well as two starting strings S1 and S2 of corresponding Fibonacci sequence of strings.

Input file format

Input file contains a single string T, consisting of lowercase Latin letters.

Output file format

Output file must contain 3 lines: integer n followed by strings S1 and S2.

If there are several optimal solutions, output any of them.

Constraints

2 ≤ |T| ≤ 106

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
oxax
3
xax
o
2
cabccab
5
ab
c
3
axaxax
4
ax
ax

Задача F. Длинный текст и много слов (revisited)

Автор:A. Klenin   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Имеется текст и N слов. Длина текста составляет L символов, длина каждого слова — от 1 до 1000 символов. Требуется для каждого слова определить, входит ли оно в текст. Все слова и текст состоят из маленьких латинских букв.

Формат входного файла

В первой строке входного файла содержится текст, во второй — число N, в следующих N строках — слова.

Формат выходного файла

В выходном файле должны содержаться N чисел 1 или 0, обозначающих, что соответствующее слово входит или не входит в текст.

Ограничения

1 ≤ L ≤ 250000, 1 ≤ N ≤ 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
longlongstring
2
short
string
0 1

Задача G. Поврежденный XML

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:xml.in   Ограничение памяти:256 Мб
Выходной файл:xml.out  

Условие

Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.

XML-строка состоит из открывающих и закрывающих тегов.

Открывающий тег начинается с открывающей угловой скобки < (ASCII 60), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка > (ASCII 62). Примеры открывающих тегов: <a>, <dog>.

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш / (ASCII 47), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов: </a>, </dog>.

XML-строка называется корректной, если она может быть получена по следующим правилам:

Например, представленные ниже строки:

являются корректными XML-строками, а такие строки как: не являются корректными XML-строками.

Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.

Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

Формат входного файла

Входной файл содержит одну строку, которая заменой ровно одного символа может быть превращена в корректную XML-строку. Строка во входном файле заканчивается переводом строки.

Формат выходного файла

Выходной файл должен содержать корректную XML-строку, которая может быть получена из строки во входном файле заменой ровно одного символа на другой. Если вариантов ответа несколько, можно вывести любой.

Ограничения

Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы <, > и /.

Примеры тестов

Входной файл (xml.in) Выходной файл (xml.out)
1
<a></b>
&lt;b&gt;&lt;/b&gt;
2
<a><aa>
&lt;a&gt;&lt;/a&gt;
3
<a><>a>
&lt;a&gt;&lt;/a&gt;
4
<a/</a>
&lt;a&gt;&lt;/a&gt;

Задача H. Abracadabra

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:sufpref.in   Ограничение памяти:256 Мб
Выходной файл:sufpref.out  

Условие

Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.

В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t1, t2, …, tn и набор из m строк-образцов s1, s2, …, sm. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.

Требуется написать программу, которая по заданному числу n, n словам словаря t1, t2, …, tn, заданному числу m и m строкам-образцам s1, s2, …, sm вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.

Система оценивания

Правильные решения для тестов, в которых 1 ≤ n ≤ 100, 1 ≤ m ≤ 100, будут оцениваться из 30 баллов.

Формат входного файла

Первая строка входного файла содержит целое число n. Последующие n строк содержат слова t1, t2, …, tn, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 106. Словарь не содержит пустых слов.

Затем следует строка, содержащая целое число m. Последующие m строк содержат строки-образцы s1, s2, …, sm, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 106. Никакая строка-образец не является пустой строкой.

Формат выходного файла

Выходной файл должен содержать m чисел, по одному на строке. Для каждой строки-образца в порядке, в котором они заданы во входном файле, следует вывести количество слов словаря, для которых она является супрефиксом.

Ограничения

1 ≤ n, m ≤ 200 000

Примеры тестов

Входной файл (sufpref.in) Выходной файл (sufpref.out)
1
4
abacaba
abracadabra
aa
abra
3
a
abra
abac
4
2
0

0.635s 0.022s 27