考虑分块加根号分治。

对于字符串长度大于根号的，个数小于根号，时间线性单根空间线性单根 将答案存起来前缀和，O(1)解决 |S_k| 大于根号的散块情况。

分块，将序列分成几个块，满足每个块的字符串长度总和为根号级别（单个长度>根号的单成一块），发现块数可能接近根号，不会证。

对于整块，建AC自动机，跑对每个串的答案，线性单根，单次单根完成散块情况。

对于 |S_k| 小于根号的散块情况，由于散块字符串长度总和小于根号，可以暴力 kmp 或建AC自动机，单次单根。

总的应该是线性单根，适当调块长，应该可以做到 $S\sqrt{n}$。