在常数时间和线性 space 中找到两个字符串的 LCP
finding LCP of two strings in constant time and linear space
问题是这样的：
假设S是一组字符串，我们知道S中所有字符串在n中的总长度。我们必须找到一个 space O(n) 的数据结构，它在 O(1) 中找到 LCP(s,t) LCP是字符串之间最长的公共前缀s,t.
起初我想我可以使用散列，因为我们可以在恒定时间内检查数字，如果我们预散列，我们可以在恒定时间内找到子字符串 strings.But 我认为这行不通因为它需要更多 space 并且经过一些搜索我发现解决方案可能在于使用 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))，对于适合可观测宇宙的任何计算机来说，它可以被视为一个相当小的常数。
问题是这样的：
假设S是一组字符串，我们知道S中所有字符串在n中的总长度。我们必须找到一个 space O(n) 的数据结构，它在 O(1) 中找到 LCP(s,t) LCP是字符串之间最长的公共前缀s,t.
起初我想我可以使用散列，因为我们可以在恒定时间内检查数字，如果我们预散列，我们可以在恒定时间内找到子字符串 strings.But 我认为这行不通因为它需要更多 space 并且经过一些搜索我发现解决方案可能在于使用 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))，对于适合可观测宇宙的任何计算机来说，它可以被视为一个相当小的常数。