Problem A. 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

Задача B. Сравнения подстрок ≡

Автор:std.alg   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Дана строка. Нужно уметь отвечать на запросы вида: равны ли подстроки [a… b] и [c… d].

Формат входных данных

Сперва строка S из строчных латинских букв. Далее число M — количество запросов.

В следующих M строках по четыре целых числа — запросы a, b, c, d.

Формат выходных данных

Выведите M строк, по одному ответу для каждого запроса. Ответ должен быть Yes, если подстроки совпадают, и No в противном случае.

Ограничения

0 ≤ M ≤ 105, 1 ≤ a ≤ b ≤ |S|, 1 ≤ c ≤ d ≤ |S|, 1 ≤ |S| ≤ 105.

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

№ Стандартный вход Стандартный выход
1 
trololo
3
1 7 1 7
3 5 5 7
1 1 1 5
 
Yes
Yes
No

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

Автор:Жюри летних сборов, И. Туфанов   Ограничение времени: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

Задача D. Наибольшая общая подстрока ≡

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

Условие

Найдите наибольшую общую подстроку строк s и t.

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

Первая строка входного файла содержит строку s, вторая — t (1 ≤ |s|, |t| ≤ 100,000). Строки состоят из строчных латинских букв.

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

Выведите одну строку — наибольшую общую подстроку строк s и t. В случае, если ответ не единственный, выведите минимальный лексикографически.

Ограничения

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

№ Входной файл (common.in) Выходной файл (common.out)
1 
ababb
abacabba
 
aba

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
0.415s 0.027s 21