Задача 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

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

Автор: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

Задача 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

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

Автор: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
0.355s 0.016s 21