标签: lcs

您将获得一系列数字,您需要从给定输入中找到最长的增加子序列(不必连续).

我找到了这个链接(维基百科上增长最快的子序列)但需要更多解释.

如果有人能帮助我理解O(n log n)实现,那将非常有用.如果你能用一个例子解释算法,那将非常感激.

我也看到了其他帖子,我不明白的是:L = 0表示i = 1,2,...... n:二元搜索最大正j≤L,使得X [M [j]] <X [i](或设置j = 0,如果没有这样的值存在)上面的语句,从哪里开始二进制搜索？如何初始化M [],X []？

我在网上搜索了一个C++ Longest Common Substring实现,但未能找到一个像样的.我需要一个返回子串本身的LCS算法,因此它不仅仅是LCS.

不过,我想知道如何在多个字符串之间做到这一点.

我的想法是检查两个字符串之间的最长字符串,然后检查所有其他字符串,但这是一个非常缓慢的过程,需要在内存上管理许多长字符串,使我的程序非常慢.

知道如何为多个字符串加速这个吗？谢谢.

重要编辑 我给出的一个变量确定了最长公共子串需要的字符串数,因此我可以给出10个字符串,并找到它们的LCS(K = 10)或LCS为4他们,但我不知道哪个4,我必须找到最好的4.

我试图找到3个或更多字符串的最长公共子序列.维基百科的文章很好地描述了如何为2个字符串执行此操作,但我不太确定如何将其扩展为3个或更多字符串.

有很多库可以找到2个字符串的LCS,所以我想尽可能使用其中一个.如果我有3个字符串A,B和C,找到A和B的LCS作为X是有效的,然后找到X和C的LCS,或者这是错误的方法吗？

我在Python中实现了如下:

import difflib

def lcs(str1, str2):
    sm = difflib.SequenceMatcher()
    sm.set_seqs(str1, str2)
    matching_blocks = [str1[m.a:m.a+m.size] for m in sm.get_matching_blocks()]
    return "".join(matching_blocks)

print reduce(lcs, ['abacbdab', 'bdcaba', 'cbacaa'])

这输出"ba",但它应该是"baa".

我有一个关于在R中找到最长公共子字符串的问题.在StackOverflow上搜索几个帖子时,我了解了qualV包.但是,我看到这个包中的LCS函数实际上找到了string1中存在的所有字符,即使它们不是连续的.

为了解释,如果字符串字符串1:" HEL LO"字符串2:" HEL 12345lo"我希望可以将输出为HEL,但是我得到的输出为hello.我一定做错了什么.请参阅下面的代码.

library(qualV)
a= "hello"
b="hel123l5678o" 
sapply(seq_along(a), function(i)
    paste(LCS(substring(a[i], seq(1, nchar(a[i])), seq(1, nchar(a[i]))),
              substring(b[i], seq(1, nchar(b[i])), seq(1, nchar(b[i]))))$LCS,
          collapse = ""))

我也尝试了Rlibstree方法,但我仍然得到不连续的子串.此外,子串的长度也与我的预期不同.请参阅下文.

> a = "hello"
> b = "h1e2l3l4o5"

> ll <- list(a,b)
> lapply(data.frame(do.call(rbind, ll), stringsAsFactors=FALSE), function(x) getLongestCommonSubstring(x))
$do.call.rbind..ll.
[1] "h" "e" "l" "o"

> nchar(lapply(data.frame(do.call(rbind, ll), stringsAsFactors=FALSE), function(x) getLongestCommonSubstring(x)))
do.call.rbind..ll.
                21

关于它们如何工作,我想知道低级工作的东西:

1. 什么会引发合并冲突？
2. 工具是否也使用上下文来应用补丁？
3. 他们如何处理实际上没有修改源代码行为的更改？例如,交换函数定义位置.

关于安全性,事实上,巨大的Linux内核存储库是他们安全的证明.但我想知道以下几点:

1. 关于用户应该注意的工具是否有任何警告/限制？
2. 算法是否被证明不会产生错误的结果？
3. 如果没有,是否有实施/论文提出集成测试,至少证明它们在经验上没有错误？像BrianKorver和JamesCoplien这些论文的内容.
4. 同样,Linux存储库应该足以满足前一点,但我想知道一些更通用的东西.源代码,即使在更改时也不会发生太大变化(特别是因为实现了算法和语法限制),但是安全性是否可以推广到通用文本文件？

编辑

好的人,我正在编辑,因为问题含糊不清,答案没有解决细节问题.

Git/diff/patch详细信息

Git似乎默认使用的统一差异格式基本上输出三个东西:变化,变化周围的上下文以及与上下文相关的行号.这些东西中的每一个可能同时也可能没有同时更改,因此Git基本上必须处理8种可能的情况.

例如,如果在上下文之前添加或删除了行,则行号将不同; 但是如果上下文和更改仍然相同,那么diff可以使用上下文本身来对齐文本并应用补丁(我不知道这是否确实发生).现在,其他案件会发生什么？我想知道Git如何决定自动应用更改以及何时决定发出错误并让用户解决冲突的详细信息.

可靠性

我非常确定Git是完全可靠的,因为它确实具有完整的提交历史并且可以遍历历史.我想要的是一些指向学术研究和有关这方面的参考资料,如果它们存在的话.

仍然有点与这个主题相关,我们知道Git/diff将文件视为通用文本文件并在线上工作.此外,diff使用的LCS算法将生成一个试图最小化变化数量的补丁.

所以这里有一些我想知道的事情:

1. 为什么使用LCS而不是其他字符串度量算法？
2. 如果使用LCS,为什么不使用度量​​的修改版本来考虑底层语言的语法方面？
3. 如果使用考虑到语法方面的这种指标,它们能否带来好处？在这种情况下的好处可能是任何东西,例如,更清洁的"责备日志".

同样,这些可能是一个巨大的主题,欢迎学术文章.

我正在寻找一种(空间)高效的LCS算法实现,用于C++程序.输入是两个整数的随机访问序列.
我目前正在使用维基百科页面中关于LCS的动态编程方法.但是,它在内存和时间中具有O(mn)行为,并且对于较大的输入而言存在内存错误.
我读过Hirschberg的算法,它大大提高了内存使用率,Hunt-Szymanski和Masek以及Paterson.由于实现这些并非易事,我更愿意在现有实现的数据上尝试它们.有谁知道这样的图书馆？我想,因为文本差异工具很常见,所以应该有一些开源库吗？

问题:需要两个字符串之间的LCS长度.字符串的大小最多为100个字符.字母表是通常的DNA,4个字符"ACGT".动态方法不够快.

我的问题是我正在处理很多对(我看到的数百万的等级).我相信我已经将LCS_length函数的调用减少到最小可能,因此使程序运行得更快的唯一方法是使用更高效的LCS_Length函数.

我已经开始实施通常的动态编程方法.这给出了正确答案,希望能够正确实施.

#define arrayLengthMacro(a) strlen(a) + 1
#define MAX_STRING 101

static int MaxLength(int lengthA, int lengthB);

/* 
 * Then the two strings are compared following a dynamic computing
 * LCS table algorithm. Since we only require the length of the LCS 
 * we can get this rather easily.
 */
int LCS_Length(char *a, char *b)
{
    int lengthA = arrayLengthMacro(a),lengthB = arrayLengthMacro(b), 
        LCS = 0, i, j, maxLength, board[MAX_STRING][MAX_STRING];

        maxLength = MaxLength(lengthA, lengthB);

    //printf("%d %d\n", lengthA, lengthB);
    for (i = …

我有两个字符变量(对象的名称),我想提取最大的公共子字符串.

a <- c('blahABCfoo', 'blahDEFfoo')
b <- c('XXABC-123', 'XXDEF-123')

我想要以下结果:

[1] "ABC" "DEF"

作为输入的这些向量应该给出相同的结果:

a <- c('textABCxx', 'textDEFxx')
b <- c('zzABCblah', 'zzDEFblah')

这些例子具有代表性.字符串包含标识元素,每个向量元素中的其余文本是常见的,但未知.

是否有解决方案,在以下某个地方(按优先顺序):

1. 基地R.

2. 推荐套餐

3. CRAN上提供的软件包

假设重复的答案不符合这些要求.

为了找到将给定字符串转换为回文所需的最小插入次数,我找到了字符串(lcs_string)及其反向的最长公共子序列.因此,要进行的插入次数是length(s) - length(lcs_string)

知道要插入的数量,应该采用什么方法来找到等效的回文串？

例如 :

1)azbzczdzez

所需插入次数:5 Palindrome字符串:azbzcezdzeczbza

虽然同一根弦可能存在多个回文弦但我只想找到一个回文？

我不明白O(2^n)最长公共子序列算法的递归函数的复杂性。

通常，我可以将这个符号与算法的基本操作（在这种情况下是比较）的数量联系起来，但这一次在我看来没有意义。

例如，有两个长度相同的字符串5. 在最坏的情况下，递归函数计算251比较。并且2^5甚至不接近该值。

谁能解释这个函数的算法复杂性？

def lcs(xstr, ystr):
    global nComp
    if not xstr or not ystr:
        return ""
    x, xs, y, ys = xstr[0], xstr[1:], ystr[0], ystr[1:]
    nComp += 1
    #print("comparing",x,"with",y)
    if x == y:
        return x + lcs(xs, ys)
    else:
        return max(lcs(xstr, ys), lcs(xs, ystr), key=len)