最近，我正在学习如何使用树来解决最长的常见子串问题。在学习了Wiki和其他在线资源之后，我发现我们应该使用后缀树来查找最长的公共子字符串。正如维基所说：
一组字符串中最长的公共子字符串可以通过为字符串构建一个通用后缀树来找到，然后从它下面的子树中的所有字符串中找到具有叶节点的</em
浏览 7提问于2014-09-23得票数 2
回答已采纳
2回答
最长公共前缀数组
、、
以下是string MISSISSIPPI的Suffix array和LCP array信息。我知道LCP提供了关于str[i - 1]和str[i]之间最长的公共前缀长度的信息。如何获得该字符串任意两个后缀之间的最大公共前缀长度。例如，我想要MISSISSIPPI和ISSIPPI之间最长的<
浏览 3提问于2012-01-03得票数 7
回答已采纳
我可以每次使用两个字符串来执行最长的公共子字符串。但请考虑下面的3个字符串：这里我们看到前两个字符串的lcs是ABZD。但是，当这将与第三个字符串相比时，lcs的长度将为零。但很明显，法团是"C“。如何使用后缀数组找到n个字符串中最长的公共子<
浏览 8提问于2021-10-12得票数 1
2回答
我的代码工作，我正在寻找更聪明的想法，以提高效率？
对于字符串相似性，它被定义为最长的公共前缀长度，例如，"abc“和"abd”为2，"aaa“和"aaab”为3。问题是计算字符串S及其所有后缀的相似性，包括作为第一个后缀的本身。例如，对于S="ababaa"，后缀是“ababaa”、"baba
浏览 6提问于2016-02-16得票数 0
回答已采纳
我有一个后缀数组SA和一个数组L，它在两个连续的后缀之间存储 (最长的公共前缀)的长度，即它也被描述为。如何使用这个数组L来找到给定的两个后缀x和y之间的LCP(x，y)？
浏览 4提问于2012-06-10得票数 4
2回答
我正在研究后缀数组及其用于计算两个后缀最长的公共前缀。消息来源说：
即lcp(x,y)=min{ lcp(x,x+1),lcp(x+1,x+2),.....,lcp(y-1,y) }，其中x和y是字符串的两个索引，从<em
浏览 2提问于2013-04-21得票数 0
回答已采纳
1回答
是否有一个有效的算法来寻找两个不同字符串的最长公共后缀和前缀？字母表的大小是无界的。
形式上，设字符串S= wa和T= bw，其中a，b，w是子串。给定S和T，如何找到最长的这样的w？
浏览 1提问于2016-10-01得票数 0
2回答
输入：返回与A大小相同的数组A，其中Output[i]是S[0..A[i]]和S最长匹配后缀的长度。S = "ababa"示例输出：我所拥有的最天真的算法是，对于每一个A[i]，只需要匹配S[0..A
浏览 5提问于2015-10-07得票数 5
回答已采纳
如何在Scala中找到两个字符串的最长公共前缀？我也许可以编写一种“命令式”解决方案(在s(i) == t(i)时，索引索引在字符串上运行)，但我正在寻找一种“函数式”解决方案(例如，无需显式更新i变量)。
浏览 4提问于2011-11-12得票数 13
回答已采纳
如果我想为两个字符串找到最长的公共子字符串，那么在时间/空间复杂性方面，哪种方法会更有效:使用DP的后缀数组？DP会产生具有O(m*n)时间复杂度的O(m*n)空间，后缀数组方法的时间复杂度是多少？( 1)计算后缀O(m) + O(n) 2)将其排序为O(m+n log2(m+n)) 3)为m+n-1字符串寻找最长的<
浏览 2提问于2013-03-14得票数 1
我正在使用python，并且我必须编写一个函数来查找字符串列表中最长的公共前缀字符串。
例如，输入参数为["flower", "flow", "flight"]，输出为"fl"。如果输入字符串之间没有公共前缀，则输出为空字符串。
浏览 3提问于2020-11-01得票数 2
我试图从多个固定长度字符串的相同位置(总共有700个字符串，每个字符串有25个字母)找到所有可能最长的公共子序列。最长的公共子序列必须至少包含3个字母，并且至少属于3个字符串。test1 = "abcdeug";String test3 = "abydnpq";
String test4
浏览 1提问于2013-05-22得票数 2
回答已采纳
1回答
假设我构造了一个后缀数组，即一个整数数组，以字典顺序表示字符串所有后缀的起始位置。示例:对于字符串str=abcabbca，suffixArray[] = [7 3 0 4 5 1 6 2]
i Suffix LCP of str and strstring 0
现在构建了这个suffixArray，我希望在str (
浏览 2提问于2012-06-17得票数 2
回答已采纳
我不想直接解决这个问题的根源，但这是一个S2 = "panama"
为了提高搜索k-th最小子字符串的效率，我对这个排序集进行了预处理，以添加关于后缀与其前身<em
浏览 1提问于2013-01-11得票数 3
回答已采纳
假设我有两个字符串，s1 = "1234"和s2 ="34567"，因此s1和s2之间最长的公共后缀前缀是"34"。我想知道是否有任何pythonic方法可以真正快速地获得这个匹配部分("34")。我可以像下面这样用一种天真的方式来完成，但我想知道是否有有趣的库函数或算法来完成这项工作。elif i > 0:
浏览 59提问于2019-10-29得票数 1
回答已采纳
2回答
给出一个字符串列表，例如：在列表中至少有两个字符串上找到最长的前缀：列表将通过输入来填充，
浏览 5提问于2017-11-02得票数 1
回答已采纳
1回答
在POSIX awk和Gawk中，如何在字符串中找到正则表达式的所有匹配？更具体地说，根据以下两个目标之一，查找由gsub内置函数替代的所有匹配：仅将匹配作为目标字符串的子字符串。
实现第一个目标意味着实现第二个目标。在POSIX awk中，是否有一个内置功能可以实现这两个目标之一？match内置函数是否只找到最左边和最长</
浏览 0提问于2017-07-18得票数 6
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
