如何以最优时间复杂度统计以指定字符串为后缀的字符串数量

给定两个字符串数组A、B，要求对B中的每一个字符串s，统计数组A中以s为后缀的字符串总个数。约束条件如下：

• 数组A、B的元素个数范围均为1~10^5
• 两个数组中单个字符串的长度范围均为1~100
  朴素解法采用双重循环逐一匹配后缀，时间复杂度为O(N²)，在1e5的数据规模下必然超时，需要效率更高的实现方案。

后缀匹配最讨巧的处理方式就是做字符串反转：把所有字符串倒序之后，原串的后缀会直接变成新串的前缀，而后缀统计问题就转换成了经典的前缀统计问题，用前缀字典树（Trie）就能做到线性时间复杂度，完全适配当前的数据规模。
如果不想手写Trie，也可以用后缀哈希计数的方案，两者复杂度处于同一量级，Trie的优势是不存在哈希碰撞，结果100%精确。

• 初始化Trie结构：每个节点包含对应字符集的子节点指针（纯小写字母场景下就是26个分支，可根据实际字符集大小调整），以及一个count字段，记录有多少个字符串经过当前节点，初始值为0。
• 构建Trie索引：遍历数组A的每一个字符串，先将字符串反转，从根节点开始逐字符插入：每走到对应字符的节点，就把该节点的count值加1；如果对应字符的子节点不存在，新建节点后再继续往下遍历。
• 执行查询：遍历数组B的每一个查询串s，同样先将s反转，从Trie根节点开始逐字符匹配：如果中途找不到对应字符的子节点，说明A中没有以s为后缀的字符串，当前查询结果直接记0；如果顺利走完反转后s的所有字符，当前停留节点的count值就是符合要求的字符串总数。

额外说明：如果查询串s的长度比A中某个字符串长，反转后匹配时自然会因为走不到终点返回0，不需要额外写边界判断逻辑。

• 时间复杂度：构建Trie的总耗时为A中所有字符串的长度之和，即O(Σ|Ai|)；处理所有查询的总耗时为B中所有字符串的长度之和，即O(Σ|Bi|)。按单字符串最长100、数组最多1e5个元素计算，总操作量在2*10^7级别，远低于常规编程语言的超时阈值，相比朴素O(N²)解法性能提升了3~4个数量级。
• 空间复杂度：最坏情况是A中所有字符串反转后没有任何公共前缀，总节点数等于A中所有字符串的长度之和，同样是1e7级别，常规开发环境的内存完全可以承载。

如果觉得Trie实现起来麻烦，也可以直接用哈希表做计数：遍历A中每一个字符串，枚举它的所有后缀（比如字符串"abc"的后缀为"abc"、"bc"、"c"），把每个后缀作为key存入哈希表，对应的value值累加1。最后对B中的每个查询串s，直接读取哈希表中key为s的value即可，key不存在则返回0。
这个方案的时间、空间复杂度和Trie方案基本一致，毕竟单串最长只有100，每个串枚举所有后缀的操作量完全在可接受范围内。缺点是存在哈希碰撞的概率，工程上可以用双哈希（用两个不同哈希函数计算值，联合作为key）降低碰撞概率，稳定性略逊于Trie。

内容的提问来源于stack exchange，提问作者Akhil Sharma