如何找到n个字符串中不同子字符串的个数

Question

给定length <=10^5的n个字符串。

输入:“aa ab ac ad”

输出:8 (“a”,”b”,”c”,”d”,”aa”,”ab”,”ac”,”ad”)

输入:“aab bcd”

输出:10 (“a”,”b”,”c”,”d”,”aa”,”ab”,”bc”,”cd”,”aab”,”bcd”)

更新:

后缀树是一种解决方案。但是它占用更多的内存。

除了后缀树，还有其他解决方案吗?

Answer 1

后缀树。除了设置后缀树之外，您不需要做任何事情，它实际上是一个列出任何字符串或字符串集的所有不同子字符串的结构。