我正在寻找一个Python库,用于从一组字符串中查找最长的公共子字符串.有两种方法可以解决这个问题:
实施的方法并不重要.重要的是它可以用于一组字符串(不仅仅是两个字符串).
我知道这是一个有点被打败的话题,但是我已经达到了可以从已经回答的问题中得到的帮助.
这是针对Rosalind项目问题的LREP.我正在尝试在字符串中找到最长的k-peated子字符串,并且我已经提供了后缀树,这很好.我知道我需要使用每个节点的后代叶子数来注释后缀表,然后找到带有>=k后代的节点,最后找到这些节点中最深的节点.理论上我已经确定了.
我从以下资源中获得了很多帮助(哎呀,我只能发布2个):
我可以从根到每个叶子获取路径,但我无法弄清楚如何以这样的方式预处理树,以便我可以从每个节点获得后代的数量.我有一个单独的算法,适用于小序列,但它具有指数复杂性,所以对于较大的东西,它需要太长时间.我知道使用DFS我应该能够以线性复杂度执行整个任务.为了使这个算法起作用,我需要能够在不到5分钟的时间内获得长度约为40,000的最长k-peat.
这是一些示例数据(第一行:sequence,第二行:k,后缀表格式:) parent child location length:
CATACATAC$
2
1 2 1 1
1 7 2 1
1 14 3 3
1 17 10 1
2 3 2 4
2 6 10 1
3 4 6 5
3 5 10 1
7 8 3 3
7 11 5 1
8 9 6 5
8 10 10 1
11 12 6 5
11 13 10 1 …在n个字符的序列S中; 每个字符可能在序列中出现多次.你想找到S的最长子序列,其中所有出现的相同字符都在一个地方;
对于前者 如果S = aaaccaaaccbccbbbab,那么最长的这样的子序列(答案)是aaaaaaccccbbbb ie = aaa__aaacc_ccbbbb.
换句话说,S中出现的任何字母字符可能只出现在子序列中的一个连续块中.如果可能,给出一个多项式时间算法来确定解.
string algorithm substring dynamic-programming longest-substring
我想比较两个ArrayLists并返回Java中最大的相似性子集.所以我想比较列表的部分而不仅仅是单个值.
例:
list 1 list 2
F A
A B
B C
C F
D D
Z Z
A
F
C
最大的子集:
Arraylist: [A,B,C]
第二个最大的子集应该是:
ArrayList: [D,Z]
我怎样才能有效地做到这一点？(不使用超过2个for循环)
retainAll()不起作用,retainAll()返回相等的值,而不是最大的子集.
编辑 我想作为输出,在最大子集之前列出,最大子集,在最大子集之后列出.通过示例输出应该是:
[[F],[null]],[A,B,C],[[D,Z,A,F,C],[F,D,Z]]
有没有人知道R包解决了最长的常见子串问题？我正在寻找可以对矢量起作用的快速的东西.
我已经绞尽脑汁待了几天,研究出一系列或封闭形式的等式来解决以下问题:
具体来说:给定长度为N的所有字符串,从L字母的字母表中开始(以'A'开头,例如{A,B},{A,B,C},...),这些字符串中有多少包含与模式匹配的子字符串:'A',超过1不 - 'A','A'.该模式的标准正则表达式将是A[^A][^A]+A.
可能的串的数量是很简单的:L ^Ñ.对于N和L的小值,简单地创建所有可能的组合并使用正则表达式来查找与模式匹配的子串也是非常实用的.在R:
all.combinations <- function(N, L) {
apply(
expand.grid(rep(list(LETTERS[1:L]), N)),
1,
paste,
collapse = ''
)
}
matching.pattern <- function(N, L, pattern = 'A[^A][^A]+A') {
sum(grepl(pattern, all.combinations(N, L)))
}
all.combinations(4, 2)
matching.pattern(4, 2)
我想出了以下内容,适用于N <7:
M <- function(N, L) {
sum(
sapply(
2:(N-2),
function(g) {
(N - g - 1) * (L - 1) ** g * L ** (N - g - 2) …问题：
给定一个包含 N 个字符的字符串 S (N <= 200 000)，找出至少出现两次的最长子字符串的长度（子字符串可以重叠）。
我的解决方案：
这是我尝试过的：
int main()
{
std::string s;
std::cin >> s;
int max = 0;
typedef std::string::const_iterator sit;
sit end = s.end();
for(sit it1 = s.begin(); it1 != end; ++it1)
for(sit it2 = it1 + 1; it2 != end; ++it2)
max = std::max(max, std::mismatch(it1, it1 + (end - it2), it2).first - it1);
std::cout << max;
}
题：
但是，上述解决方案在 O(n^3) 中运行时将获得 TLE。有什么方法可以改进它以便它可以在 O(n.logn) 中运行？
python中是否有内置函数返回两个列表中最长公共子序列的长度？
a=[1,2,6,5,4,8]
b=[2,1,6,5,4,4]
print a.llcs(b)
>>> 3
我试图找到最长的常见子序列,然后得到它的长度,但我认为必须有一个更好的解决方案.
我试图找到小于 1000 的数字，它在除以 1 时产生最长的重复数字串。我有一个十进制数字列表，必须找到那些具有最长重复序列的数字。
这是我到目前为止所拥有的
numbers = [*2..999]
decimal_representations = numbers.map { |number| 1.to_f/number }
decimal_representations.map!(&:to_s)
我可以使用正则表达式生成一个三维数组。正则表达式/(.+)\1+/产生一个重复子串的数组。我想找到最长的子串，所以我使用了 enumerable 的max_by函数。
decimal_representations.map! { |decimal| decimal.scan(/(.+)\1+/).max_by(&:length) }.flatten
我必须压缩我的数组以删除nil元素
decimal_representations.compact!
然后我可以找出哪个长度最长。
decimal_representations.max_by(&:length)
我得到0090009009，但我无法确定哪个数字具有该十进制值，因为我从数组中删除了 nil 元素。
有任何想法吗？
我想用来difflib.SequenceMatcher从两个字符串中提取最长的公共子字符串。我不确定是否发现错误或对的文档有误解find_longest_match。这一点令我感到困惑：
换句话说，在所有最大匹配块中，返回最早在a中开始的一个，在所有最大匹配块中最早在a中开始的，返回最早在b中的一个。
（https://docs.python.org/3.5/library/difflib.html#difflib.SequenceMatcher.find_longest_match）
比较字符串X this is a test和this is a test X，子字符串X实际上是一个最大的块：它不能扩展（即，它是包含最大的）。此外，它是文本A中的第一个此类最大块。但是，它肯定不是最长的公共子字符串。我强烈怀疑这不是find_longest_match应该找到的。
实际上，在此示例中，find_longest_match确实找到了最长的公共子字符串：
>>> l = len("X this is a test")
>>> matcher = difflib.SequenceMatcher(None, "X this is a test", "this is a test X")
>>> matcher.find_longest_match(0, l, 0, l)
Match(a=2, b=0, size=14)
但是，对于其他字符串，我似乎可以挑起上面描述的“查找第一个最大块”（对长字符串，很抱歉，如果我将它们缩短，示例会以某种方式中断）：
>>> s1 = "e-like graph visualization using a spanning tree-driven layout technique with constraints specified by layers and …