问题标签 [longest-prefix]

如果我有一个私有 IP 地址块，例如 171.58.0.0/12，这是否意味着我基本上按位与 171.58.0.0 的 32 位版本与 32 位 1，其中最后 12 位为 0 , 以获得该范围内可接受的私有 IP 地址的最长前缀？

获取前缀可接受的私有 IP 地址？

谢谢！

这是为一个相对琐碎的问题想出最优雅的 JavaScript、Ruby 或其他解决方案的挑战。

这个问题是最长公共子串问题的一个更具体的例子。我只需要在数组中找到最长的公共起始子字符串。这大大简化了问题。

例如，最长的子串[interspecies, interstelar, interstate]是“inters”。但是，我不需要在[specifics, terrific].

我已经通过在 JavaScript 中快速编写一个解决方案来解决这个问题，作为我关于 shell-like tab-completion ( test page here )的答案的一部分。这是该解决方案，稍作调整：

此Gist 中提供了此代码以及Ruby 中的类似解决方案。您可以将要点克隆为 git repo 以进行尝试：

我对这些解决方案不太满意。我有一种感觉，它们可能会以更优雅的方式和更少的执行复杂性来解决——这就是我发布这个挑战的原因。

我将接受我认为最优雅或最简洁的解决方案作为答案。例如，这是我想出的一个疯狂的 Ruby hack——&在 String 上定义运算符：

JavaScript 或 Ruby 的解决方案是首选，但你可以用其他语言展示聪明的解决方案，只要你解释发生了什么。请仅使用标准库中的代码。

更新：我最喜欢的解决方案

我选择了kennebec的JavaScript 排序解决方案作为“答案”，因为它让我觉得既意外又天才。如果我们忽略实际排序的复杂性（让我们想象它被语言实现无限优化），解决方案的复杂性只是比较两个字符串。

其他很棒的解决方案：

• FM 的“regex greed”需要一两分钟才能掌握，但随后它的优雅就让你眼前一亮。Yehuda Katz 也做了一个正则表达式解决方案，但它更复杂
• commonprefix在 Python 中——Roberto Bonvallet 使用了一个用于处理文件系统路径的特性来解决这个问题
• Haskell one-liner很短，好像被压缩了一样，很漂亮
• 简单的 Ruby 单线

感谢参与！正如您从评论中看到的，我学到了很多东西（甚至是关于 Ruby）。

您可以在所有标准标签前使用浏览器特定前缀吗？

例如

上述有效的 CSS 是否可以确保 Firefox 与所有其他浏览器具有不同的底部填充？

我需要有关可用于 URL 上“最长前缀匹配”的任何标准 python 包的信息。我已经浏览了两个标准包http://packages.python.org/PyTrie/#pytrie.StringTrie & 'http://pypi.python.org/pypi/trie/0.1.1' 但它们似乎没有对 URL 上的最长前缀匹配任务很有用。

例如，如果我的设置有这些 URL 1->http://www.google.com/mail , 2->http://www.google.com/document, 3->http://www.facebook.com ， ETC..

现在，如果我搜索“http://www.google.com/doc”，那么它应该返回 2，搜索“http://www.face”应该返回 3。

我想确认是否有任何标准的 python 包可以帮助我做到这一点，或者我应该实现一个 Trie 来进行前缀匹配。

我不是在寻找一种正则表达式的解决方案，因为它随着 URL 数量的增加而无法扩展。

非常感谢。

我有一个循环通过 DAO 执行 N 次查询。就我而言，我有一个属性值为“123456789”的对象。在第一轮中，它对特定表执行查询以获取列C1等于“123456789”的所有记录。

在第二轮中，它在同一个表上执行查询以获取列C1等于“12345678”的所有记录。依此类推，直到找到具有最长前缀的记录。

我想，与其多次执行这个查询，不如只执行一次另一个查询，它将字符串“123456789”作为参数，并返回具有C1最长前缀“123456789”的列的记录。但我不知道如何使用 Hibernate（如果可能）来做到这一点，或者您是否有其他解决方案。我正在使用 MySQL。

（我看过这篇文章，但我想知道是否有办法用 Hibernate 做到这一点。）

我试图在 ruby​​ 的字符串数组中找到所有常见的子序列，而不仅仅是最长的单个子序列。

这意味着如果输入是

[“aaaF 你好”，“aaaG 你好”，“aaaH 你好”]

预期的输出是

[“aaa”，“你好”]

我一直在搞乱最长的单子序列算法，但不知道如何获得适当的输出。大多数方法的问题是它们在最终数组中还有其他元素，例如“a”、“aa”、“h”、“he”、“hel”、“hell”

在 PostgreSQL 中获得准确和快速查询以获得最长前缀匹配的最佳方法是什么？

是吗：

我打算在更新中使用。有任何想法吗？

我需要对表中的列运行最长匹配前缀，而不仅仅是单个值。对于单个值，我使用类似SELECT value, prefix as lmp FROM aTable WHERE SUBSTRING(value,1, LENGTH(prefix)) = prefix ORDER BY prefix DESC limit 1.

问题是，如果它是针对许多记录进行的，它将需要进行表扫描并逐个获取值，并且将需要客户端和服务器之间的大量流量。

有没有办法在涉及子查询但不涉及存储过程的单个查询中做到这一点？我正在使用 PostgreSQL 8.4。

我正在使用这个程序来计算后缀数组和最长公共前缀。

我需要计算两个字符串之间的最长公共子字符串。

为此，我连接字符串，A#B然后使用这个算法。

我有后缀数组sa[]和LCP[]数组。

LCP[]最长的公共子串是数组的最大值。

为了找到子串，唯一的条件是在相同长度的子串中，字符串B中第一次出现的那个应该是答案。

为此，我维持 LCP[] 的最大值。如果LCP[curr_index] == max，那么我确保left_index子字符串 B 的 小于 的先前值left_index。

但是，这种方法并没有给出正确的答案。错在哪里？

如何计算后缀数组的 LCP 数组？它不一定是最有效的。O(n log n) 或 O(n) 都可以。如果可能的话，一些相对容易编码的东西。