Codeforces Round 254 (Div. 1) |
---|
Закончено |
DZY очень любит строки. Он коллекционирует особо ценные строки.
В Китае многие люди любят использовать строки со своими инициалами, например: xyz, jcvb, dzy, dyh.
Однажды DZY нашел особо ценную строку s. Услышав об этом, несколько пар хороших друзей пришло навестить DZY. Первого друга i-й пары зовут ai, второго друга пары зовут bi. Каждой паре стало интересно, есть ли в особо ценной строке подстрока, содержащая оба имени пары. Если такая существует, друзья хотели бы найти подстроку минимальной длины, чтобы запомнить ее на удачу.
Пожалуйста, помогите DZY, для каждой пары найдите минимальную длину подстроки s, которая содержит ai и bi, или же укажите, что искомая подстрока не существует.
Подстрока s это строка slsl + 1... sr для некоторых чисел l, r (1 ≤ l ≤ r ≤ |s|). Длина такой подстроки равна (r - l + 1).
Строка p содержит некоторую другую строку q, если p имеет подстроку, равную q.
В первой строке записана строка s (1 ≤ |s| ≤ 50000).
Во второй строке записано неотрицательное целое число q (0 ≤ q ≤ 100000) — количество пар друзей. В каждой из следующих q строк описывается пара имен — две строки через пробел, ai и bi (1 ≤ |ai|, |bi| ≤ 4).
Гарантируется, что все строки состоят только из строчных букв латинского алфавита.
Для каждой пары выведите строку, содержащую единственное целое число — минимальная длина требуемой подстроки. Если искомой подстроки не существует, выведите -1.
xudyhduxyz
3
xyz xyz
dyh xyz
dzy xyz
3
8
-1
abcabd
3
a c
ab abc
ab d
2
3
3
baabcabaaa
2
abca baa
aa aba
6
4
Кратчайшие подстроки для первого примера таковы: xyz, dyhduxyz.
Кратчайшие подстроки для второго примера таковы: ca, abc и abd.
Кратчайшие подстроки для третьего примера таковы: baabca и abaa.
Название |
---|