Підрядки в словнику
Обмеження: 2 сек., 512 МіБ
Зеник і Марічка мають набір із \(n\) рядків \(s_1, s_2, ... s_n\). Також у них є рядок \(t\).
Їх цікавить, скільки підрядків \(t[l..r]\) (\(1 \le l \le r \le |t|\)) містять хоча б одне входження довільного слова із набору \(s\). Допоможіть їм знайти цю кількість.
Вхідні дані
У першому рядку вхідних даних задано одне ціле число \(n\) — кількість рядків у наборі \(s\).
У наступних \(n\) рядках задано непусті рядки \(s_i\), по одному на рядок.
У останньому рядку задано рядок \(t\).
Вихідні дані
Виведіть одне ціле число — відповідь на задачу.
Обмеження
\(1 \le n, |t| \le 3 \cdot 10^5\),
сумарна довжина рядків \(s_i\) не перевищує \(3 \cdot 10^5\),
усі рядки складаються лише із малих англійських букв.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 3 aa aba ca abcabaacbaccaa | 71 |
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|