给定 n 个字符串。对于由 l 和 r 组成的 q 查询，我应该为序列 [l， r] 中的所有字符串对输出 LCP(最长的公共前缀)。是否有任何数据结构(段树，芬威克...)可以帮助解决这个问题？我怎么能在这里预先计算任何东西，记住 n 和 q 都是 <= 10^5。所有字符串长度的总和是 <= 10^5？
除了蛮力解决方案，我没有其他想法...
假设你得到了一些字符串。首先，您需要对它们进行排序。
1. hello | 1. broad
2. wi-fi | 2. brother
3. brother | 3. hell
4. sister | 4. hello
5. broad | 5. siam
6. siam | 6. sial
7. sial | 7. sister
8. sit | 8. sit
9. hell | 9. wi-fi
然后，创建一个带有索引的数组，以了解排序数组中每个字符串的位置。
index in orignal - 1 2 3 4 5 6 7 8 9
index in sorted - 4 9 2 7 1 5 6 8 3
现在，对于每个查询，您需要在排序数组中找到最小和最大索引。基于这两个指数找到LCP。请参阅示例。
例 1
l,r = 1,5
排序数组中的相应索引4 9 2 7 1。最小和最大指数是1和9。因此，单词broad和wi-fi都在查询中，LCP 是空字符串。
例 2
l,r = 6,8
排序数组中的相应索引5 6 8。最小和最大指数是5和8。因此，siam和sit字词都在查询中，而 LCPsi。
复杂性
对所有字符串进行排序。要正确估计此处的复杂性，您需要正确建模可能的输入。
对于每个查询，您需要对最大和最小索引进行线性时间搜索，然后查找两个字符串的 LCP。