Автор задачи и разработчик: Егор Юлин
Для начала заметим, что в терминах строк требуется найти количество пар $$$(s_i, s_j)$$$, для которых $$$\mathtt{lcp}(s_i, s_j)$$$ лежит в наборе $$$t$$$. Здесь за $$$\mathtt{lcp}$$$ обозначен наибольший общих префикс двух строк.
Данную задачу можно решать при помощи бора. Причем бор можно строить как на строках $$$s_i$$$, и затем обрабатывать $$$t_i$$$ и считать ответ, так и наоборот.
Построим бор на строках второго набора ($$$t$$$), и в каждой вершине бора будем хранить $$$\mathtt{term}_v$$$ — заканчивается ли в ней какой-то $$$t_i$$$, и $$$\mathtt{cnt}_v$$$ — количество строк $$$s_i$$$, имеющих префикс $$$v$$$. Чтобы посчитать все $$$\mathtt{term}$$$, достаточно запомнить их при построении, а чтобы посчитать $$$\mathtt{cnt}$$$, будем по очереди обрабатывать $$$s_i$$$, проходить по бору и увеличивать это количество на $$$1$$$ в каждой пройденной вершине.
Тогда обработка строки $$$s_i$$$ по мере спуска в боре выглядит следующим образом: если в текущей вершине есть строка из второго набора, то к ответу прибавим $$$\mathtt{cnt}_v - \mathtt{cnt}_{v + c}$$$, где $$$c$$$ — следующий символ $$$s_i$$$. Это количество соответствует числу строк $$$s_j$$$, которые начинаются на $$$v$$$, но не на $$$v + c$$$, то есть $$$\mathtt{lcp}$$$ которых с $$$s_i$$$ в точности равен $$$v$$$. После этого перейдём в следующую вершину бора.
Такое решение работает за суммарную длину всех строк.