javascript - 搜索最长前缀

Question

假设，它有一个字符串数组 D。给定一个字符串 Q，我想在 D 中找到与 Q 具有最长公共(public)前缀的字符串。

我不想要复杂的数据结构，但它仍然应该比线性扫描更快。

有没有一种解决方案可以巧妙地对 D 进行排序，并且只进行一次二分查找？

谢谢!

编辑

澄清:当然，如果只做一次，单次扫描比排序快。但是，我需要在固定的 D 上做很多这样的查找，所以这就是我寻找预先计算的数据结构的原因。

Answer 1

根据D中的字符创建一棵树:

每个节点包含字符和一个子节点列表。

例如，如果 D 是

 a
 ab
 ac
 ace
 d

然后

• 有 2 个顶级节点 a 和 d
• d 没有 child
• a 有 2 个 child - b 和 c
• b 没有 child
• c 有 1 个 child - e
• e 没有 child

查找(并添加到树中!)基本上是遍历节点，直到没有匹配的子节点为止。

例如，假设 Q=af。有一个包含 Q[0]=a 的顶级节点，但它没有包含 Q[1]=f 的子节点，所以最长的前缀是 a。 a 节点的所有子节点表示 D 中的字符串，这些字符串与 Q 具有最长的公共(public)前缀，特别是 a , ab, ac, ace.

查找和添加操作在字符串长度上都是线性的，因此结构的创建需要 O(sum(len(x) for x in D)) 时间，查找是 O( len(Q)).