这是问题所在：
假设 S 是一组字符串，我们知道 n 中S中所有字符串的总长度。我们必须找到一个空间为 O(n( 的数据结构，该结构在O(1(中找到 LCP(s，t(，其中 LCP 是字符串s，t之间最长的公共前缀。
起初，我认为我可以使用散列，因为如果我们预先散列字符串，我们可以在常量时间内检查数字并在常量时间内找到子字符串。但我认为这行不通，因为它需要更多的空间，经过一番搜索，我发现解决方案可能在于使用 Trie，后缀数组，也许还有 LCA 和 RMQ。我想我已经接近答案了，但不知道这些概念如何协同工作以快速提供 LCP 的数据结构！
感谢您的阅读
我想我知道他们正在寻找的答案。
首先，为所有字符串构造一个 trie。 trie 中的每个节点都可以包含指向以该前缀开头的字符串的指针和长度。将每个字符串映射到该字符串结束的trie中的最终节点。
现在，当给定一对字符串(大概您被告知字符串i和字符串j(时，返回字符串的问题是一个找到最不常见的祖先的问题，然后将该对返回(pointer_to_start_of_string, length)。
但是trie可以写成一棵树，然后Tarjan的离线最低共同祖先算法(见 https://www.geeksforgeeks.org/tarjans-off-line-lowest-common-ancestors-algorithm/(可以用来预处理该树，以非常快速地回答LCA问题。
从技术上讲，这不是O(1).然而，对于任何适合可观测宇宙的计算机来说，它可以被视为一个相当小的常数O(inverse_ackermann(n))。