Codeforces Round 857 (Div. 1) |
---|
Закончено |
Для этого он взял строку $$$t$$$ и набор из $$$n$$$ строк $$$s_1$$$, $$$s_2$$$, $$$s_3$$$, ..., $$$s_n$$$. У Филиппа есть $$$m$$$ запросов, в $$$i$$$-м из них Филипп хочет взять подстроку строки $$$t$$$ с $$$l_i$$$-го по $$$r_i$$$-й символ, и посчитать число её подстрок, которые совпадают с какой-то строкой из набора. Более формально, Филипп хочет посчитать число пар позиций $$$a$$$, $$$b$$$, таких что $$$l_i \le a \le b \le r_i$$$, и подстрока строки $$$t$$$ с $$$a$$$-го по $$$b$$$-й символ совпадает с некоторой строкой $$$s_j$$$ из набора.
Подстрокой строки $$$t$$$ с $$$a$$$-го по $$$b$$$-й символ называется строка, полученная из $$$t$$$ путём удаления $$$a - 1$$$ символа из начала и $$$|t| - b$$$ символами из конца, где $$$|t|$$$ обозначает длину строки $$$t$$$.
Филипп уже решил эту задачу, а сможете ли вы?
В первой строке два целых положительных числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 500\,000$$$) — число строк в наборе и количество запросов.
Во второй строке дана единственная строка $$$t$$$, состоящая из строчных букв английского алфавита ($$$1 \le |t| \le 5 \cdot 10^6$$$).
В следующих $$$n$$$ строках описываются строки из набора. В $$$i$$$-й из них дана единственная строка $$$s_i$$$, состоящая из строчных букв английского алфавита. Обозначим за $$$S$$$ суммарную длину всех строк из набора. Гарантируется, что $$$S \le 10^6$$$, а так же что все строки $$$s_i$$$ различны.
В следующих строках вводятся запросы. В $$$i$$$-й из них даны два целых положительных числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le |t|$$$) — левая и правая граница подстроки $$$t$$$ из $$$i$$$-го запроса.
В единственной строке выведите $$$m$$$ целых чисел, $$$i$$$-е из них должно быть равно ответу на $$$i$$$-й запрос.
3 5 abacaba aba a ac 1 7 1 3 2 7 2 5 4 5
7 3 5 3 1
4 4 abcdca ab ca bcd openolympiad 1 5 2 2 2 6 1 6
2 0 2 3
В первом примере в первом запросе требуется у всей строки посчитать число подстрок, которые входят в набор. Со строкой «aba» совпадают подстроки $$$[1, 3]$$$ и $$$[4, 6]$$$. Со строкой «a» совпадают подстроки $$$[1, 1]$$$, $$$[3, 3]$$$, $$$[5, 5]$$$, $$$[7, 7]$$$. Со строкой «ac» совпадает подстрока $$$[3, 4]$$$. Всего получается, что 7 подстрок строки «abacaba» совпадают со строками из набора.
Во втором запросе от исходной строки берется подстрока с 1 по 3 позицию, это строка «aba». В неё строка «aba» входит 1 раз, строка «a» входит 2 раза и строка «ac» не входит ни одного раза как подстрока. В третьем запросе от исходной строки берется подстрока с 2 по 7 позицию, это строка «bacaba». В неё строка «aba» входит 1 раз, строка «a» входит 3 раза и строка «ac» входит 1 раз как подстрока.
Название |
---|