Задача №114555. Конкатенация с пересечением
У Васи было три строки \(a\), \(b\) и \(s\), состоящие из строчных символов латинского алфавита. Длины строк \(a\) и \(b\) равны \(n\), длина строки \(s\) равна \(m\).
Вася решил вырезать некоторую подстроку строки \(a\), затем вырезать некоторую подстроку строки \(b\) и сконкатенировать их. Более формально, он выбирает некоторый отрезок \(1 \leq l_1 \leq r_1 \leq n\) и отрезок \(1 \leq l_2 \leq r_2 \leq n\), вырезает подстроки \(a[l_1, r_1] = \overline{a_{l_1} a_{l_1 + 1} \ldots a_{r_1}}\) и \(b[l_2, r_2] = \overline{b_{l_2} b_{l_2 + 1} \ldots b_{r_2}}\). Затем, он рассматривает строку \(a[l_1, r_1] + b[l_2, r_2] = \overline{a_{l_1} a_{l_1 + 1} \ldots a_{r_1} b_{l_2} b_{l_2 + 1} \ldots b_{r_2}}\).
Теперь Васю заинтересовал вопрос, сколькими способами он может выбрать так пару отрезков, что выполнены следующие условия:
- отрезки \([l_1, r_1]\) и \([l_2, r_2]\) пересекаются, то есть существует хотя бы одно целое число \(x\), такое что \(l_1 \leq x \leq r_1\) и \(l_2 \leq x \leq r_2\);
- полученная Васей в итоге строка \(a[l_1, r_1] + b[l_2, r_2]\) равна строке \(s\).
Помогите ему и посчитайте количество таких способов. Две пары отрезков считаются различными, если первые отрезки пар не совпадают или вторые отрезки пар не совпадают.
В первой строке заданы два целых числа \(n\) и \(m\) (\(1 \leq n \leq 500\,000, 2 \leq m \leq 2 \cdot n\)) — длина строк \(a\) и \(b\) и длина строки \(s\) соответственно.
Во второй строке задана строка \(a\) длины \(n\), состоящая из строчных букв латинского алфавита.
В третьей строке задана строка \(b\) длины \(n\), состоящая из строчных букв латинского алфавита.
В четвертой строке задана строка \(s\) длины \(m\), состоящая из строчных букв латинского алфавита.
Выведите одно целое число — количество способов выбрать пару отрезков, удовлетворяющую Васиным условиям.
Перечислим все пары отрезков, которые мог выбрать Вася в первом примере:
- \([2, 2]\) и \([2, 5]\);
- \([1, 2]\) и \([2, 4]\);
- \([5, 5]\) и \([2, 5]\);
- \([5, 6]\) и \([3, 5]\);
Пару отрезков \([5, 6]\) и \([2, 4]\) Вася выбрать не мог, потому что они не пересекаются. Пару отрезков \([2, 3]\) и \([3, 5]\) Вася выбрать не мог, потому что \(a[2, 3] + b[3, 5] = \overline{abaaa} \neq s\).
Тесты к этой задаче состоят из семи групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Группа | Баллы | Дополнительные ограничения | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 9 | \(n \leq 20\) | 0 | |
| 2 | 10 | \(n \leq 100\) | 0, 1 | |
| 3 | 12 | \(n \leq 500\) | 0, 1, 2 | |
| 4 | 20 | \(n \leq 5\,000\) | 0, 1, 2, 3 | |
| 5 | 10 | \(n \leq 100\,000\) | 0, 1, 2, 3, 4 | |
| 6 | 17 | \(m \leq 100\) | 0, 1 | |
| 7 | 12 | – | – | Все символы s равны. |
| 8 | 10 | – | 0 – 7 | Offline-проверка. |
6 5 aabbaa baaaab aaaaa
4
5 4 azaza zazaz azaz
11
9 12 abcabcabc xyzxyzxyz abcabcayzxyz
2