Зеник і рядки
Обмеження: 2 сек., 256 МіБ
У Зеника є набір n рядків si та рядок t.
Йому стало цікаво, наскільки рядок t гармонійно поєднується з набором.
Зеник визначає гармонійність рядка t й набору s як ∑ni=1f(si,t), де f(s,t)=∑|t|i=1|lcp(s,ti..|t|)|, |t| — довжина рядка t, ti..|t| — суфікс рядка t, що починається в позиції i, lcp(s,t) — найдовший спільний префікс рядків s і t.
Допоможіть Зенику порахувати гармонійність його рядків.
Вхідні дані
У першому рядку задано t.
У другому рядку записано ціле число n — кількість рядків у наборі.
У наступних n рядках задано si.
Вихідні дані
В одному рядку виведіть ціле число — відповідь на задачу.
Обмеження
1≤|t|≤105,
1≤n≤105,
1≤∑ni=1|si|≤105,
усі рядки складаються з малих літер латинської абетки.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
algotester 3 tester te algo | 16 |
Джерело: NextGen Contest 1