Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дана строка s. Ответьте на m запросов вида: равны ли подстроки s[a..b] и s[c..d].
В первой строке ввода записана строка s (1 ≤ |s| ≤ 10^5).
Во второй строке записано целое число m — количество запросов (0 ≤ m ≤ 10^5).
В следующих m строках четверки чисел a, b, c, d (1 ≤ a ≤ b ≤ |s|, 1 ≤ c ≤ d ≤ |s|).
Выведите m строк. Выведите Yes, если подстроки совпадают, и No иначе.
Входные данные
trololo
3
1 7 1 7
3 5 5 7
1 1 1 5
Выходные данные
Yes
Yes
No
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Постройте Z-функцию для заданной строки s.
Первая строка входного файла содержит s (1 ≤ |s| ≤ 10^6). Строка состоит из букв латинского алфавита.
Выведите значения 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| ≤ 10^6). Строки состоят из букв латинского алфавита.
В первой строке выведите количество вхождений строки p в строку t. Во второй строке выведите в возрастающем порядке номера символов строки t, с которых начинаются вхождения p. Символы нумеруются с единицы.
Входные данные
aba
abaCaba
Выходные данные
2
1 5
Ограничение по времени на тест: 5 секунд
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дан набор слов и текст, требуется определить для каждого слова, присутствует ли оно в тексте как подстрока.
В первой строке дан текст (не более 10^6 строчных латинских букв). Далее дано число M — количество слов в словаре.
В следующих M строках записаны слова (не более 30 строчных латинских букв). Слова различны и отсортированы в лексикографическом порядке.
Суммарная длина слов в словаре не более 10^5.
M строк вида Yes, если слово присутствует, и No иначе.
Входные данные
trololo
3
abacabadabacaba
olo
trol
Выходные данные
No
Yes
Yes
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Даны K строк из маленьких латинских букв. Требуется найти их наибольшую общую подстроку.
В первой строке число K (1 ≤ K ≤ 10).
В следующих K строках — собственно K строк (длины строк от 1 до 10 000).
Наибольшая общая подстрока.
Входные данные
3
abacaba
mycabarchive
acabistrue
Выходные данные
cab