Sample test cases?

You didn't tell us whether the test is finished or not. We shouldn't help you if the test is not finished yet.

Reverse all strings, so task becomes about prefix instead of suffix. Create segment tree, where each node have a trie that contains all strings from this node's corresponding segment (each string will be in $$$log~n$$$ tries, so memory will be $$$23 \cdot n~log~n$$$). With trie it's easy to count necessary sum of all string nested in this trie in $$$O(23)$$$, so overall query's complexity will be $$$O(23 \cdot log~n)$$$.

create a trie with reversed strings and store indices of strings in each node in sorted order then query for reversed string, you can find out for each each prefix of reversed string how many strings from given range match this prefix

I solved it using map and policy based data structure My solution