Codeforces Round 820 (Div. 3) |
---|
Закончено |
Вам даны две непустые строки $$$s$$$ и $$$t$$$, состоящие из латинских букв.
За один ход вы можете выбрать вхождение строки $$$t$$$ в строку $$$s$$$ и заменить его на точки.
Ваша задача — за минимальное количество ходов убрать все вхождения строки $$$t$$$ в строке $$$s$$$, а также посчитать, сколько существует различных последовательностей ходов минимальной длины.
Две последовательности ходов считаются различными, если множества индексов, в которых начинаются убираемые вхождения строки $$$t$$$ в $$$s$$$, различаются. Например, множества $$$\{1, 2, 3\}$$$ и $$$\{1, 2, 4\}$$$ считаются различными, множества $$$\{2, 4, 6\}$$$ и $$$\{2, 6\}$$$ — тоже, а множества $$$\{3, 5\}$$$ и $$$\{5, 3\}$$$ — нет.
Например, пусть строка $$$s =$$$ «abababacababa», а строка $$$t =$$$ «aba». Мы можем убрать все вхождения строки $$$t$$$ за $$$2$$$ хода, заменив вхождения строки $$$t$$$ на $$$3$$$-й и $$$9$$$-й позициях на точки. В этом случае строка $$$s$$$ пример вид «ab...bac...ba». Также можно вырезать вхождения строки $$$t$$$ на $$$3$$$-й и $$$11$$$-й позициях. Всего есть две различные последовательности ходов минимальной длины.
Так как ответ может быть большим, выведите его по модулю $$$10^9 + 7$$$.
Первая строка входных данных содержит единственное целое число $$$q$$$ ($$$1 \le q \le 50$$$) — количество наборов входных данных. Далее следуют описания наборов.
Первая строка каждого набора содержит непустую строку $$$s$$$ ($$$1 \le |s| \le 500$$$), состоящую из строчных латинских букв.
Вторая строка каждого набора содержит непустую строку $$$t$$$ ($$$1 \le |t| \le 500$$$), состоящую из строчных латинских букв.
Гарантируется, что сумма длин строк $$$s$$$ по всем наборам входных данных не превосходит $$$500$$$. Аналогично, гарантируется, что сумма длин строк $$$t$$$ по всем наборам входных данных не превосходит $$$500$$$.
Для каждого набора входных данных выведите два целых числа — минимальное количество ходов и количество различных оптимальных последовательностей, взятое по модулю $$$10^9 + 7$$$.
8abababacababaabadddddddddddxyzxyzxyzabcabcdabacabaabacaabcdefaaaaaaaaaaaaaaaaaaa
2 2 1 4 2 1 0 1 1 1 0 1 8 1 3 6
Первый набор входных данных разобран в условии.
Во втором наборе достаточно заменить любое из четырёх вхождений.
В третьем наборе строка $$$s$$$ является конкатенацией двух строк $$$t =$$$ «xyz», поэтому существует единственная оптимальная последовательность из $$$2$$$ ходов.
В четвёртом и шестом наборах строка $$$s$$$ изначально не содержит вхождений строки $$$t$$$.
В пятом наборе строка $$$s$$$ содержит ровно одно вхождение строки $$$t$$$.
Название |
---|