问题标签 [longest-prefix]

包递归；

出于某种原因，我没有得到正确的输出。碰巧有一件小事我错过了。非常感谢任何形式的帮助。提前致谢

问题描述： 参考：Fun With Strings

根据问题描述，找到所有可能子字符串（对于给定字符串）的LCP长度总和的简单方法如下：

基于对 LCP 的进一步阅读和研究，我发现了这个文档，它指定了一种使用称为Tries的高级数据结构有效地查找 LCP 的方法。我实现了一个 Trie 和一个 Compressed Trie（后缀树），如下所示：

我的问题是如何继续找到 LCP 的长度。我可以通过获取分支节点的标签字段来获取 LCP，但是如何计算所有可能子字符串的 LCP 的长度？

我想到的一种方法是如何使用分支节点、其包含 LCP 的标签字段以及分支节点的子节点来查找所有 LCP 长度的总和（最低公共祖先？）。但我仍然很困惑。我该如何进一步进行？

注意：也有可能我对这个问题的处理方法是错误的，所以请也针对这个问题提出其他方法（考虑时间和空间复杂度）。

链接到类似的未回答问题：

• 给定字符串的所有子串对的 LCP 总和
• 所有子字符串和一个字符串的最长公共前缀长度

代码和理论参考：

• 液晶面板
• 特里
• 压缩特里

更新1：

根据@Adarsh Anurag 的回答，我在 trie 数据结构的帮助下提出了以下实现，

从 Trie 结构中，我删除了变量isEndOfWord，而是将其替换为counter. 此变量跟踪重复的子字符串，这将有助于计算具有重复字符的字符串的 LCP。但是，上述实现仅适用于具有不同字符的字符串。我已经尝试实现@Adarsh 为重复字符建议的方法，但不满足任何测试用例。

更新2：

根据@Adarsh 的进一步更新答案和不同测试用例的“反复试验”，我似乎在重复字符方面取得了一些进展，但它仍然无法按预期工作。这是带有注释的实现，

此外，这里有一些示例测试用例（预期输出），

对于测试用例 2 和 3（部分输出），上述实现失败。请提出解决此问题的方法。解决此问题的任何其他方法也可以。

假设自治系统 AS0 从其对等体接收到以下两个公告：

AS1：42.0.0.0/8，路径长度为 10

AS2：42.0.0.0/16，路径长度为 20

现在，目标地址为 42.0.0.1 的数据包将被 AS0 路由到哪里？

到 AS1 是因为它有更短的路径，还是到 AS2 因为它有更长的前缀？

此代码（改编自前缀-后缀代码）对于较大的语料库非常慢：

输出：gaf

任何有效替代方案的选择？

我正在寻找一种方法来读取 CIDR 地址列表并将它们转换为二进制字符串。输入是一个文件，其中包含多行操作、地址和目的地：

ADD 192.168.20.16/28 A

FIND 255.255.255.0

REMOVE 192.168.20.16/28 A

如何将这些地址转换为二进制？例如：

192.168.20.191至11000000.10101000.00010100.10111111

192.168.20.16/28至11000000.10101000.00010100.00010000

192.168.0.0/16至11000000.10101000.00000000.00000000

编写一个函数来查找字符串数组中最长的公共前缀字符串如果没有公共前缀，则返回一个空字符串“”。示例：输入：strs = ["flower","flow","flight"] 输出："fl" 我是编码新手，尝试解决这个问题（来自 leetcode）。我的方法是搜索字符串之间最短的字符串，这是我的代码，我不知道我在哪里做错了，似乎while循环根本不起作用。如果有人可以帮助我，我将不胜感激。这是我的代码：

输入：[“flower”，“flow”，“flight”] 输出：“flo” 预期输出：“fl”

我刚来这地方。我正在 Leetcode 上尝试关于最长公共前缀的 C# 问题。我知道这个问题已经解决了很多次。我只是很难理解为什么我的代码在某些条件下不起作用。当输入 ["flower","flow","flight"] 被输入时，它工作得很好并得到输出 "fl"。但是，当我输入 ["ab", "a"] 时，我突然得到一个 IndexOutOfRangeException。有谁知道为什么？这是我的代码：