最长公共子序列是否存在低于 O(n^2) 的算法？
比如这个问题，O(n^2)的解法会超时-----------------------分割线-----------------------问了下学长，那个题因为字符集比较小可以用位压缩的技术来优化，不过这个是常数优化，渐进复杂度还是n^2的
按投票排序
起床怒答一发。低于 O(n^2) 的通用方法好像是没有的（起码我不知道），虽然大家都是 O(n^2) 的复杂度，但是算法和算法之间也是有差距的。普通的DP方法，无论是时间还是空间上，都是非常不优秀的，都是 O(n^2)。实际上LCS在日常生活中是非常常见的，比如说 diff 本质上就是一个 LCS，只不过 diff 可能会允许近似解。如果真的 LCS 的实现大多是DP（或者某些可能的变种），那么想想当你 git diff 一个近万行的程序的时候，那画面不得太美了？（10000^2 的计算量，得跑一会儿了，并且想想你的内存……）顺着这个思路，注意到就算是你 git diff 了一个近万行的程序，但是实际上你可能只修改了不到一百行。读到这里，细心的读者一定发现了，衡量一个 diff 算法的优劣指标不应该仅仅由长度 n 决定，还应该由差异数量 d 决定！现在广泛采用的 diff 算法，也就是题注问的 LCS 算法，基本上采用的是 Eugene Myers 的论文 An O(ND) Difference Algorithm and its Variations () 上面写的方法的变种，在论文中提到的方法在时间上是很好的，在空间上不知比DP厉害到哪里去了：期望的时间复杂度是 O(N + M + D^2)最坏的时间复杂度是 O((N+M) * D)可优化成 O((N+M)log(N+M) + D^2)空间复杂度是 O(N + M)论文写得还是很清楚的，跟着看就行了。另外，如果你真的拿两个差异很大的文件去 diff ，你会发现它仍然跑得飞快，这就牵扯到很多近似解的方法了，不过这些近似解的方法也都是从这篇论文的方法衍生出去的。因为我没有去了解，而且也不符合题主的需求，所以就不多提了。有兴趣的可以去看看 diffutils 和 libxdiff 的代码，里面有写注释（其实也只标注了说这是一个 heuristic method ，没有仔细讲为什么）我上个学期因为在实现一个 simplified git 所以接触到了这个东西，看了上面两个库的代码，发现看不懂 T_T 于是只好自己对着论文写了，有需要的可以看： 只包含了这篇论文里面的算法，不包括各种启发式的近似解，不过实测 O(ND) 的复杂度已经很优秀了。====== 广告时间 ======当时我们有做了个 benchmark 发现我们的 simplified git 的效率稍稍比 git 更高了点，这是我们当时演讲的 slides:
。其实我只是来求 star 的：======
Update ======刚刚看到@马融 马老师点了一下赞，瞬间得到了一大堆赞，受宠若惊。
似乎没听说过严格小于 O(n^2) 的算法，但是存在一般情况下 O(n log n) 的算法。对于 A，B 两个串，将 A 中每个字符替换成在 B 中间出现的位置的逆序列，例如原串为A="abacd"B="cabbab"字符 'a' 在 B 中出现的位置为 2, 5，字符 'b' 在 B 中出现的位置为 3, 4, 6，字符 'c' 出现的位置为 1，字符 'd' 没有出现。那么 A 序列将被替换成为(5, 2), (6, 4, 3), (5, 2), (1), (?)每一个括号代表原来的 A、B 两串相同字符的匹配，如下图：但是匹配必须是递增的，也就是每个括号里选一个数，选出的数必须递增。将括号里的数反序排列是为了方便限制 “每个括号里选一个数” 的条件。但是匹配必须是递增的，也就是每个括号里选一个数，选出的数必须递增。将括号里的数反序排列是为了方便限制 “每个括号里选一个数” 的条件。这是 LCS（最长公共子序列） 到 LIS（最长递增子序列） 的经典转化。只需要找到 “(5, 2), (6, 4, 3), (5, 2), (1), (?)” 里面的递增子序列即可。对于长度为 n 的最长递增子序列，存在基于动态规划的严格 O(n log n) 算法，这个可以自己搜索。但是 A → (5, 2), (6, 4, 3), (5, 2), (1), (?) 这一步，序列变长了，一般来说不会退化，整个算法还是约为 O(n log n) 的。但是 A="aaaaa" B="aaaaaa" 这样的数据就会退化成 O(n^2 log n)。
若字符集为常数，则可低于O(MN)设字符集为C, 将动态规划中n*n的矩阵拆分（n/t）^2个t＊t的小矩阵,其中t为1/2*log以c为底n， 在预处理中小矩阵有c^2t种，每个小矩阵需要t^2时间计算，所以预处理需要o(n(logn)^2)，这样每个可能的小矩阵的结果都已经计算完最后针对n＊n大矩阵中的每个t＊t小矩阵填入返回值（由于小矩阵的返回值仅与它上面和左面边上的值有关，因此检查每个小矩阵的时候仅需要输入上面和左面边上的值，也只需要返回下面后右面边上的值，这四条边都是O(t），因此检查一个小矩阵也需要O(t）)因为总共需要检查（n/t）^2个小矩阵,检查一个小矩阵需要O(t）,最后得到右下角的值就需要（n/t）^2＊t=(n^2)/t = O((n^2)/logn)， 小于O(MN)
谢邀，lcs问题O(mn)是下界了，如果数据特殊，可以有针对性的优化，同样推荐这个帖子。
一般采用动态规划的时间复杂度为O(MN)，没有见过比这个效果更好的。
预处理一下，将A中的元素换为B中的对应下标，然后求LIS，复杂度就是NlogN了
非特殊情况的话n^2基本是理论最好了，顶多差一些log项
(1) 对序列B排序(2) 计算A中每个元素在B中的序号，并构成新序列(3) 使用LIS的方法计算最长严格递增子序列(4) 获取最长公共子序列这种算法怎么样？我试过用于计算两个01组成的字符串，发现结果不太对。求知友一起探讨下
已有帐号？
无法登录？
社交帐号登录最长公共子序列
最长公共子序列的问题很简单，就是在两个中找到最长的子序列，这里明确两个含义：
子串：表示连续的一串字符
子序列：表示不连续的一串字符。
所以这里要查找的是不连续的最长子序列，
这里为什么要使用动态规划可以说一下，简单来说动态规划是为了降低时间复杂度的一种算法，申请一个额外，来保存每一个步骤的结果，最后从这些结果中找到最优的解。
这里有个问题就是：一般来说，当前的最优解，只与当前时刻和上一时刻有关系，和其他时刻没有关系，这样才能让动态规划发生作用，降低复杂度。
其实LCS看起来很麻烦，找不到思路，如果暴力破解可能要O(n^4)了，而这个题目使用动态规划的思想也非常简单，为何相比之前的问题不好找思路呢？
是因为之前的动态规划问题例如：背包问题，生产线问题，都是一维数组空间内的结果，规划到一个线性时间内，而这个题目需要O(m*n)的时间复杂度和空间复杂度。
所以其实就是进行m*n次对比，每次保存当前的最优解，就可以了。
代码实现分析
这里有个问题，就是我们需要的结果仅仅是长度？ 还是包括这个序列串一起输出。
看下面图：
这里可以看到，我们构造的一个i*j的矩阵，这个矩阵里的内容不但包括数值（当前结果的最优解），还包括一个方向箭头，这个代表了我们回溯的时候，需要行走的方向。
所以我们这里保存两个值，可以使用两个二维矩阵，也可以使用一个结构体矩阵。
其实这个题目在动态规划来理解，也非常简单。一个状态转移函数。
这个非常好理解，其中一个字符串为0的时候，那么肯定是0了。
当两个字符相等的时候，这个时候很好理解，举例来说：
abcd 和 adcd,在遍历c的时候，发现前面只有a相等了，也就是1.
那么c相等，也就是abc和adc在匹配的时候，一定比ab和ad的长度大1，这个1就是c相等么。也就是相等的时候，是比c[i-1][j-1]大1的。
下一个更好理解了，如果不相等，肯定就是找到上一个时刻对比最大的么。
这个代码只输出了LCS的长度，而结果数组的方向我已经好了，想要遍历的，直接从后向前遍历数组就好了。
最长公共子序列(LCS)
Created by Alps on 15/8/23.
Copyright (c) 2015年 chen. All rights reserved.
#include &iostream&
using namespace std;
* 这里可以不定义长度，输入的字符串用string存储，然后利用string.c_str()来对字符串进行数组转化。 我这里为了方便没有这样做。
#ifndef MAX_LENGTH
#define MAX_LENGTH 15 //定义字符串最大长度
int MaxNum(int firstNum, int secondNum){
return firstNum & secondNum ? firstNum : secondN
//定义数组结构体
struct matrix{
typedef matrix M
int LCS(char *strA, char *strB, int lengthA, int lengthB, Matrix *resultMatrix[]){
if (lengthA == 0 || lengthB == 0) {
for (int i = 0; i & lengthA; i++) {
for (int j = 0; j & lengthB; j++) {
resultMatrix[i][j].num = 0; //设置所有默认的最长为0
resultMatrix[i][j].direct = 1; //所有默认方向变成上 0斜上，1上，-1左
for (int i = 0; i & lengthA; i++) {
for (int j = 0; j & lengthB; j++) {
if (strA[i] == strB[j]) {
resultMatrix[i+1][j+1].num = resultMatrix[i][j].num + 1;
resultMatrix[i+1][j+1].direct = 0;
resultMatrix[i+1][j+1].num = MaxNum(resultMatrix[i+1][j].num, resultMatrix[i][j+1].num);
resultMatrix[i+1][j+1].direct = resultMatrix[i+1][j].num & resultMatrix[i][j+1].num ? 1 : -1;
return resultMatrix[lengthA][lengthB].
int main(int argc, const char * argv[]) {
char *strA = (char*)malloc(sizeof(char) * MAX_LENGTH);
char *strB = (char*)malloc(sizeof(char) * MAX_LENGTH);
scanf("%s",strA);
scanf("%s",strB);
int lengthA = (int)strlen(strA);
int lengthB = (int)strlen(strB);
Matrix *resultMatrix[lengthA+1];
for (int i = 0; i &= lengthA; i++) {
resultMatrix[i] = (Matrix*)malloc(sizeof(struct matrix)* (lengthB+1));
int max = LCS(strA, strB, lengthA, lengthB, resultMatrix);
printf("%d\n",max);
std::cout && "Hello, World!\n";
以上。?Alps1992
版权声明：本文为博主原创，未经博主允许不得转载。edit 文本相似度计算，包含编辑距离，和最长公共子序列算法的结合。 Mathimatics-Numerical algorithms 数值 /人工智能 254万源代码下载-
&文件名称: edit& & [
& & & & &&]
&&所属分类:
&&开发工具: Visual C++
&&文件大小: 305 KB
&&上传时间:
&&下载次数: 107
&&提 供 者:
&详细说明：文本相似度计算，包含编辑距离，和最长公共子序列算法的结合。-xiangsudu jisuan
文件列表(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉):
&&edit\come.h&&....\Debug\BuildLog.htm&&....\.....\ed.obj&&....\.....\main.obj&&....\.....\ng.obj&&....\.....\test1.exe&&....\.....\test1.exe.embed.manifest&&....\.....\test1.ilk&&....\.....\test1.pch&&....\.....\test1.pdb&&....\.....\vc60.idb&&....\.....\vc60.pdb&&....\.....\vc90.idb&&....\.....\vc90.pdb&&....\ed.cpp&&....\lcs.cpp&&....\main.cpp&&....\ng.cpp&&....\test1.dsp&&....\test1.dsw&&....\test1.ncb&&....\test1.opt&&....\test1.plg&&....\test1.sln&&....\test1.suo&&....\test1.vcproj&&....\test1.vcproj.ghost-PC.Administrator.user&&....\Debug&&edit
&[]:文件不全
&近期下载过的用户:
&相关搜索:
&输入关键字，在本站254万海量源码库中尽情搜索：
&[] - 用来检查文件之间的相似程度
&[] - C#实现的Diff工具，能够比较两个文本文件的差异，并计算文本相似度。
&[] - 文本文件，网页内容相似度匹配hash算法源代码，用于生成文件指纹，并根据文件指纹生成文件相似度。有windows和linux2个系统的源代码。
&[] - 本程序用于文档相似度的匹配，判别文档的雷同,能够显示文档的相似率！
&[] - 文本相似度计算工具代码，这是在做搜索引擎非常需要的一个算法，对于想从事开发这方面的应用，具有不错的参考价值。
&[] - 词汇比较程序。 能够比较两个词汇的相似度程序，基于wordnet。
&[] - 实现最小编辑距离算法，并给出完整的编辑过程，完整版源码，已调试通过
&[] - 设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：
1. 删除一个字符
2. 插入一个字符
3. 将一个字符改为另一个字符
将字符串A变换为字符串B所用的最少操作数称为A到B的编辑距离，极为d(A,B)。设计一个算法，计算任意两个字符串的编辑距离。
&[] - 珍藏论文：面向双语句对检索的汉语句子相似度计算Chinese Sentences Similarity
&[] - 先对句子分词，然后根据词来比较句子的相似度，这个算法清晰易懂，欢迎下载！}