最长公共子序列算法的改进
最近找到一个改进的最长公共子序列算法，看不太懂，大家帮我分析一下这个算法，谢谢！
QMap<int, int> FileDiff::lcsx()
{//采用自主改进的LCSX算法
QMap<int, int> matchmap;
QString linetext1;
QString linetext2;
QStringList flist1;
QStringList flist2;
int M,N;
if(filelist1.length() >= filelist2.length())
{
M = filelist1.length();
N = filelist2.length();
flist1 = filelist1;
flist2 = filelist2;
}
else
{
M = filelist2.length();
N = filelist1.length();
flist1 = filelist2;
flist2 = filelist1;
}
int **array;//M>=N
array = new int *[M];
for (int i = 0; i < M; i++)
{
array[i] = new int[N];
}
qDebug()<<"初始化开始"<1000.0<<"s";
for (int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{//全部初始化为-1
array[i][j] = -1;
}
}
qDebug()<<"初始化结束"<1000.0<<"s";
double rate;
if(M>N && N==1) rate = -1.0;
else rate = (M>N)?(1.0*(M-1)/(N-1)):1.0;
int next;
int i=0, j=0;
int itmp=0, jtmp=0;
int maxmatch = 0, matchadd = 0;
int locai = 0, locaj = 0;
qDebug()<<"算法开始"<1000.0<<"s";
while(i!=M || j!=N)
{//lcsx算法开始
itmp = i;
jtmp = j;
while(array[i][j] == -1)
{
linetext1 = flist1.at(i);
linetext2 = flist2.at(j);
if(i == maxmatch) locaj = j+1;//记录待补余行的i,j位置
if(j == maxmatch) locai = i+1;
if(linetext1 == linetext2)
{
if(i == 0 || j == 0) array[i][j] = 1;
else array[i][j] = array[i-1][j-1] + 1;
if(array[i][j] > maxmatch) matchadd = 1;
}
else
{
if(i == 0 && j==0) array[i][j] = 0;
else if(i == 0) array[i][j] = array[i][j-1];
else if(j == 0) array[i][j] = array[i-1][j];
else array[i][j] = (array[i-1][j]>=array[i][j-1])?array[i-1][j]:array[i][j-1];
}
if(rate < 0) break;
next = itmp + 1 - (static_cast<int>(rate*(j+1))-static_cast<int>(rate*jtmp));//下一行要算到的位置
if(next <= maxmatch) break;
else
{
i = next-1;
j++;
if(j == N) break;
}
}
if(matchadd == 1)
{//匹配数增加了，前maxmatch行列补余格子
maxmatch++;
for (; locai < M; locai++)
{
if(array[locai][maxmatch-1] == -1) array[locai][maxmatch-1] = array[locai-1][maxmatch-1];
}
for (; locaj < N; locaj++)
{
if(array[maxmatch-1][locaj] == -1) array[maxmatch-1][locaj] = array[maxmatch-1][locaj-1];
}
matchadd = 0;
}
if(itmp+1 == M || jtmp < maxmatch)
{//这行算满了 或者 这行补余了
//跳到下一行
if(jtmp+1 != N)
{
itmp = itmp - (static_cast<int>(rate*(jtmp+1))-static_cast<int>(rate*jtmp));
if(itmp < maxmatch) itmp = maxmatch-1;
}
else itmp = M-1;
jtmp++;
}
i = itmp+1;
j = jtmp;
}
qDebug()<<"算法结束"<1000.0<<"s";
qDebug()<<"回溯开始"<1000.0<<"s";
i--;j--;
while(maxmatch > 0)
{//开始回溯
while(j >= 0)
{
j--;
if(j==-1 || array[i][j]while(i >= 0)
{
i--;
if(i==-1 || array[i][j]if(filelist1.length() >= filelist2.length()) matchmap.insert(i, j);
else matchmap.insert(j, i);
maxmatch--;
break;
}
}
break;
}
}
i--;j--;
}
qDebug()<<"回溯结束"<1000.0<<"s";
for (int i = 0; i < M; i++)
{
delete[]array[i];
}
delete[]array;
return matchmap;
}
为了方便大家比较，我把经典LCS算法也放这里
QMap<int, int> FileDiff::lcs()
{
QMap<int, int> matchmap;
QString linetext1;
QString linetext2;
int M = filelist1.length();
int N = filelist2.length();
int **array;
array = new int *[M];
for (int i = 0; i < M; i++)
{
array[i] = new int[N];
}
int i=0, j=0;
while(j!=N)
{//lcs算法开始
linetext2 = filelist2.at(j);
while(i!=M)
{
linetext1 = filelist1.at(i);
if(linetext1 == linetext2)
{
if(i == 0 || j == 0) array[i][j] = 1;
else array[i][j] = array[i-1][j-1] + 1;
}
else
{
if(i == 0 && j==0) array[i][j] = 0;
else if(i == 0) array[i][j] = array[i][j-1];
else if(j == 0) array[i][j] = array[i-1][j];
else array[i][j] = (array[i-1][j]>=array[i][j-1])?array[i-1][j]:array[i][j-1];
}
i++;
}
i = 0;
j++;
}
i = M-1;
j = N-1;
int maxmatch = array[i][j];
while(maxmatch > 0)
{//开始回溯
while(j >= 0)
{
j--;
if(j==-1 || array[i][j]while(i >= 0)
{
i--;
if(i==-1 || array[i][j]break;
}
}
break;
}
}
i--;j--;
}
for (int i = 0; i < M; i++)
{
delete[]array[i];
}
delete[]array;
return matchmap;
}
- 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7789538
- 这篇博客你也可以参考下：LCS算法：最长公共子序列
- 除此之外, 这篇博客: 算法设计与分析部分中的 2）最长公共子序列问题（LCS） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
子序列：将给定序列中零个或多个元素去掉之后得到的结果
子串：给定串中任意个【连续】的字符组成的子序列称为该串的子串
for(int i = 1;i<=m;i++){ for(int j = 1;j<=n;j++){ //i,j从1开始，所以下面用i-1和j-1使得可以从数组0元素开始 if(x[i-1]==y[j-1]) c[i][j] = c[i-1][j-1]+1; else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j]; else c[i][j]=c[i][j-1]; } }https://www.cnblogs.com/Monster-su/p/14579852.html
// 动态规划 public static void f1(char arr1[],char arr2[],int n,int m) { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(arr1[i-1]==arr2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]); } } System.out.println(dp[n][m]); } // 备忘录 public static int f2(char arr1[],char arr2[],int n,int m) { if(n==0||m==0) return 0; else if(arr1[n-1]==arr2[m-1]) dp[n][m]=f2(arr1,arr2,n-1,m-1)+1; else dp[n][m]=Math.max(f2(arr1,arr2,n-1,m),f2(arr1,arr2,n,m-1)); return dp[n][m]; }
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^
这段代码实现了一种基于经典LCS算法的改进方法，称为LCSX算法。LCSX算法的核心思想是利用文件差异的特点，通过补余操作和跳行机制，优化匹配的效率。下面对代码进行详细分析。
LCSX算法实现
LCSX算法的实现主要包括以下几个步骤：
- 初始化数组。该算法使用一个二维数组来存储LCS的长度，因此需要先创建一个大小为M*N的数组，其中M和N为两个文件的行数。在初始化时，将数组中所有元素初始化为-1。
- 计算匹配率。在LCSX算法中，为了提高匹配的效率，需要根据文件长度计算出一个匹配率。如果M>N且N=1，则将匹配率设置为-1；否则将匹配率设置为(M-1)/(N-1)。
- LCSX算法匹配。该算法使用一个while循环来遍历数组中的每个元素，并使用一个跳行机制来优化匹配效率。具体来说，当匹配率大于0时，每次匹配完一行后，将下一行要匹配的位置设为当前行的下一个位置加上匹配率的整数部分，减去上一个匹配的位置的整数部分。同时，如果待匹配的位置小于等于上一次匹配的位置，则跳过该位置，直接匹配下一个位置。
- 匹配数增加时的补余操作。当匹配数增加时，需要进行补余操作，将前maxmatch行列中未匹配的元素补全。
- 回溯操作。LCSX算法完成匹配后，还需要进行一次回溯操作，将匹配的结果保存到一个QMap<int,int>类型的变量中。
经典LCS算法实现
为了更好地理解LCSX算法，我们还将经典LCS算法的实现代码一并列出。与LCSX算法相比，经典LCS算法并没有采用跳行机制和补余操作，而是直接遍历数组进行匹配，然后再进行一次回溯操作。
总结
LCSX算法是一种基于经典LCS算法的改进方法，通过跳行机制和补余操作，可以大幅提高匹配的效率。与经典LCS算法相比，LCSX算法的时间复杂度更低，尤其是在处理大文件时，优势更为明显。