问题标签 [longest-prefix]

给定一个 IP 地址 192.168.0.1，以及一个包含存储子网 IP 地址的 next_hop_subnet 列的表，您是否发现以下 PostGRESQL 逻辑、准确性或性能方面有任何问题：

因为，可以有多个同样好的匹配，我认为除了分两步之外别无他法。有什么建议么？

获得两个数组的最长公共前缀（从原始索引 0 开始的子数组）和后缀（以原始索引 -1 结尾的子数组）的最佳方法是什么？例如，给定两个数组：

这些数组的最长公共前缀是：

这些数组的最长公共后缀是：

当原始数组中索引 0/-1 处的元素不同时，公共前缀/后缀应该是一个空数组。

在语音应用程序中，我必须找到国际电话号码前缀的最长匹配。我有一个 50K 行的费率表，存储在 CSV 文件中，该文件会定期更新为新费率（CSV 列标题包含前缀、国家/地区费率等）。该应用程序使用 REST API 来根据用户输入的电话向用户显示呼叫目的地的费用。不能使用简单的 KVS，因为有多个匹配项并且需要最长的前缀匹配项。API 受到很多打击，因此直接使用数据库太慢/太重（在此处使用 APC，但似乎没有太大区别）。我能想出的最佳算法如下所示，但在体面的机器上完成仍需要将近 1 秒。任何 PHP 算法大师有更好的方法吗？

假设有大量单个单词（不是短语）的数组，例如

给定另一个单词数组，除了“蛮力”解决方案（即连续字符串匹配）之外，从左到右查找最长共同匹配的最有效（最快）方法是什么？

例如，给定数组{"One", "two", "three", "four", "five"}，上面列表中最长的共同匹配是{"One", "two", "three", "four"}.

我有一个大约 5000 个单词的列表。我想在给定单词的这些单词中找到最长的前缀匹配。例如，在我的列表中，我有：

现在，如果我搜索 12134，结果将是 121（最长匹配）。我知道它可以通过不同的方式来完成。但是，最有效的方法应该是什么？

我目前在 Symfony2 中使用FOSElasticaBundle，我很难尝试建立一个搜索来匹配最长的前缀。

我知道 Internet 上有 100 个示例使用它来执行类似自动完成的搜索。但是，我的问题有点不同。

在自动完成类型的搜索中，数据库包含最长的字母数字字符串（字符长度），用户只提供最短的部分，假设用户键入“jho”，Elasticsearch 可以轻松提供“Jhon, Jhonny, Jhonas”。

我的问题是倒退，我想提供最长的字母数字字符串，我希望 Elasticsearch 为我提供数据库中最大的匹配。

例如：我可以提供“123456789”，我的数据库可以有 [12,123,14,156,16,7,1234,1,67,8,9,123456,0]，在这种情况下，数据库中最长的前缀匹配用户提供的号码是“123456”。

我刚开始使用 Elasticsearch，所以我真的没有接近工作设置或任何东西。

如果有任何信息不清楚或丢失，请告诉我，我会提供更多详细信息。

更新 1（使用 Val 的第二次更新）

索引：下载1800+索引

奖金问题

我想为该搜索提供一组数字，并以有效的方式获取每个数字的匹配前缀，而不必每次都执行查询

我想创建一个 MySQL 查询来查找子网表中存在的最长匹配（以四点格式的给定 IP 地址）。

最终，我想创建一个LEFT JOIN将显示一个表中的每个四点 IP 地址与另一个表中最长的匹配项相连接的一个表。我不想创建任何临时表或将其构建为嵌套查询。

我有点像 MySQL 新手，但我在想的是这样的：

这样minimum_ip_value和maximum_ip_value是给定子网中可能的最低和最高十进制格式的 IP 地址 - 例如，对于子网 172.16.0.0/16：

并且<list of subnet intervals>包含介于和subnets_table之间的所有间隔<given ip address>minimum_ip_valuemaximum_ip_value

如果一个以上的区间包含<given ip address>，那么最小的区间（即最小的子网，或最具体和“最长”的匹配）被加入。

最终，我真正想要的是subnet_id与该间隔对应的值。

所以我的问题是：

1) 我可以使用带有任意数量参数的 LEAST() 函数吗？我想比较 的每一行，或者更具体地说，比较每一行在和subnets_table之间的间隔，并选择最小的间隔。minimum_ip_valuemaximum_ip_value

2) 我可以在LEFT JOIN查询中执行所有这些计算吗？我可以接受任何快速、封装并避免重复查询相同数据的建议。

我想知道这是否甚至可以在单个查询中执行（即，不为每个 IP 地址查询子网表），但我不知道足以排除它。请告知这看起来是否行不通，所以我可以尝试另一个角度。

谢谢。

我尝试解决 leetcode 上的问题 14，即编写一个函数来查找字符串数组中最长的公共前缀字符串。这是我的代码，我期望的结果是“f”，而我得到的结果是“”。有人可以帮我吗？谢谢！

这是结果 在此处输入图像描述

我最近遇到了 KMP 算法，我花了很多时间试图理解它为什么起作用。虽然我现在确实了解基本功能，但我根本无法理解运行时计算。

我从 geeksForGeeks 网站获取了以下代码：https ://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/

该站点声称，如果文本大小为 O(n) 且模式大小为 O(m)，则 KMP 会在最大 O(n) 时间内计算匹配。它还指出可以在 O(m) 时间内计算 LPS 数组。

我真的很困惑为什么会这样。

对于 LPS 计算，请考虑： aaaaaacaaac 在这种情况下，当我们尝试计算第一个 c 的 LPS 时，我们将继续返回，直到遇到 LPS[0]，即 0 并停止。因此，本质上，我们将至少返回模式的长度直到该点。如果这种情况发生多次，时间复杂度将如何 O(m)？

我对 KMP 的运行时间有类似的困惑是 O(n)。

在发布之前，我已经阅读了堆栈溢出中的其他线程，以及有关该主题的各种其他站点。我仍然很困惑。如果有人可以帮助我了解这些算法的最佳和最坏情况以及如何使用一些示例计算它们的运行时间，我将不胜感激。再说一次，请不要建议我用谷歌搜索，我已经完成了，花了整整一周的时间试图获得任何见解，但失败了。

我在 StackOverflow 上发现了类似的问题，但我的问题不同。

给定一个字符串s包含小写字母alphabet。我想找到Longest common Prefix所有子字符串的长度。

例如

那么子串如下：

现在，LCP所有子串的长度如下

我正在使用逐个字符匹配

但是，它仍然是 O(n2)。我知道所有子字符串都相互重叠，可以进一步优化。任何人都可以帮助优化此代码吗？