• A Сравнения подстрок
• B Префикс-функция
• C Z-функция
• D Быстрый поиск подстроки в строке
• E Поиск периода
• F Подстроки-3
• G Множественный поиск
• H Множественный поиск 2
• I Множественный поиск 3
• J Суффиксный массив
• K Количество подстрок
• L Циклические сдвиги
• M Наибольшая общая подстрока

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

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

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

Выходные данные:
M строк. Выведите Yes, если подстроки совпадают, и No иначе.

Пример

Входные данные
trololo
3
1 7 1 7
3 5 5 7
1 1 1 5
Выходные данные
Yes
Yes
No

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие:
Постройте префикс-функцию для заданной строки s.

Входные данные:
Первая строка входного файла содержит s (1 ≤ |s| ≤ 106). Строка состоит из букв латинского алфавита.

Выходные данные:
Выведите значения префикс-функции строки s для всех индексов 1, 2, ..., |s|.

Пример

Входные данные
aaaAAA
Выходные данные
0 1 2 0 0 0

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие:
Постройте Z-функцию для заданной строки s.

Входные данные:
Первая строка входного файла содержит s (1 ≤ |s| ≤ 106). Строка состоит из букв латинского алфавита.

Выходные данные:
Выведите значения Z-функции строки s для индексов 2, 3, ..., |s|.

Пример

Входные данные
aaaAAA
Выходные данные
2 1 0 0 0

Входные данные
abacaba
Выходные данные
0 1 0 3 0 1

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие:
Даны строки p и t. Требуется найти все вхождения строки p в строку t в качестве подстроки.

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

Выходные данные:
В первой строке выведите количество вхождений строки p в строку t. Во второй строке выведите в возрастающем порядке номера символов строки t, с которых начинаются вхождения p. Символы нумеруются с единицы.

Пример

Входные данные
aba
abaCaba
Выходные данные
2
1 5

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие:
Дана строка s. Требуется найти минимальную по длине строку t, такую что s представима в виде конкатенации одной или нескольких строк t.

Входные данные:
Первая строка входного файла содержит s (1 ≤ |s| ≤ 106). Строка состоит из букв латинского алфавита.

Выходные данные:
Выведите длину искомой строки t.

Пример

Входные данные
abcabcabc
Выходные данные
3

Входные данные
abacaba
Выходные данные
7

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие:
Даны K строк из маленьких латинских букв. Требуется найти их наибольшую общую подстроку.

Входные данные:
В первой строке число K (1 ≤ K ≤ 10).

Выходные данные:
Наибольшая общая подстрока.

Пример

Входные данные
3
abacaba
mycabarchive
acabistrue
Выходные данные
cab

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: search4.in
вывод: search4.out

Условие:
Дан массив строк si и строка t. Требуется для каждой строки si определить, встречается ли она в t как подстрока.

Входные данные:
Первая строка входного файла содержит целое число n — число элементов в s (1 ≤ n ≤ 106). Следующие n строк содержат по одной строке si. Сумма длин всех строк из s не превосходит 106. Последняя строка входного файла содержит t (1 ≤ t ≤ 106). Все строки состоят из строчных латинских букв.

Выходные данные:
Для каждой строки si выведите «YES», если она встречается в t и «NO» в противном случае. Строки нумеруются в порядке появления во входном файле.

Пример

Входные данные
3
abc
abcdr
abcde
xabcdef
Выходные данные
YES
NO
YES

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: search5.in
вывод: search5.out

Условие:
Дан массив строк si и строка t. Требуется для каждой строки si определить, сколько раз она встречается в t как подстрока.

Входные данные:
Первая строка входного файла содержит целое число n — число элементов в s (1 ≤ n ≤ 106). Следующие n строк содержат по одной строке si. Сумма длин всех строк из s не превосходит 106. Последняя строка входного файла содержит t (1 ≤ t ≤ 106). Все строки состоят из строчных латинских букв.

Выходные данные:
Для каждой строки si выведите одно число: сколько раз она встречается в t. Строки нумеруются в порядке появления во входном файле.

Пример

Входные данные
3
abc
abcdr
abcde
xabcdef
Выходные данные
1
0
1

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 512 мегабайт
ввод: search6.in
вывод: search6.out

Условие:
Дан массив строк si и строка t. Требуется для каждой строки si найти самое левое и самое правое вхождение в t как подстроки.

Входные данные:
Первая строка входного файла содержит целое число n — число элементов в s (1 ≤ n ≤ 106). Следующие n строк содержат по одной строке si. Сумма длин всех строк из s не превосходит 106. Последняя строка входного файла содержит t (1 ≤ t ≤ 106). Все строки состоят из строчных латинских букв.

Выходные данные:
Для каждой строки si выведите два числа: индексы самой левой и самой правой позиции, в которых она встречается в t. Если строка не встречается в t ни разу, выведите  - 1  - 1. Строки нумеруются в порядке появления во входном файле. Позиции нумеруются с 0.

Пример

Входные данные
3
ab
bcd
abde
abcdab
Выходные данные
0 4
1 1
-1 -1

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 512 мегабайт
ввод: array.in
вывод: array.out

Условие:
Постройте суффиксный массив для заданной строки s, для каждых двух соседних суффиксов найдите длину максимального общего префикса.

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

Выходные данные:
В первой строке выведите |s| различных чисел — номера первых символов суффиксов строки s так, чтобы соответствующие суффиксы были упорядочены в лексикографически возрастающем порядке. Во второй строке выведите |s| - 1 чисел — длины наибольших общих префиксов.

Пример

Входные данные
ababb
Выходные данные
1 3 5 2 4
2 0 1 1

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 512 мегабайт
ввод: count.in
вывод: count.out

Условие:
Вычислите количество различных подстрок строки s.

Входные данные:
Единственная строка входного файла содержит строку s (1 ≤ |s| ≤ 400 000). Строка состоит из строчных латинских букв.

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

Пример

Входные данные
ababb
Выходные данные
11

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 512 мегабайт
ввод: shifts.in
вывод: shifts.out

Условие:
k-м циклическим сдвигом строки S называется строка, полученная перестановкой k первых символов строки S в конец строки.Рассмотрим все различные циклические сдвиги строки S и отсортируем их по возрастанию. Требуется вычислить i-ю строчку этого массива.Например, для строки abacabac существует четыре различных циклических сдвига: нулевой (abacabac), первый (bacabaca), второй (acabacab) и третий (cabacaba). После сортировки по возрастанию получится такой массив: abacabac, acabacab, bacabaca, cabacaba.

Входные данные:
В первой строке входного файла записана строка S, длиной не более 100 000 символов с ASCII-кодами от 32 до 126. Во второй строке содержится единственное целое число k (1 ≤ k ≤ 100 000).

Выходные данные:
В выходной файл выведите k-й по возрастанию циклический сдвиг строки S, или слово IMPOSSIBLE, если такого сдвига не существует.

Пример

Входные данные
abacabac
4
Выходные данные
cabacaba Входные данные
abacabac
5
Выходные данные
IMPOSSIBLE

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 512 мегабайт
ввод: common.in
вывод: common.out

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

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

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

Пример

Входные данные
bababb
zabacabba
Выходные данные
aba