最长的Common Substring：递归解决方案？

Question

常见的子串算法：

LCS(x,y) = 1+ LCS(x[0...xi-1],y[0...yj-1] if x[xi]==y[yj]
           else 0

现在动态编程解决方案已经很好理解了。但是我无法弄清楚递归解决方案。如果有多个子串，则上述算法似乎失败。

例如：

x = "LABFQDB" and y = "LABDB"

应用上述算法

1+ (x=  "LABFQD" and y = "LABD")
1+ (x=  "LABFQ" and y = "LAB")
return 0 since 'Q'!='B'

返回的值是2，我应该是3？

有人可以指定递归解决方案吗？

Answer 1

您不理解该算法，因为它不是最长公共子串的算法...

正确的公式是：

LCS(x,y) = 1+ LCS(x[0...xi-1],y[0...yj-1]) if x[xi]==y[yj]
           else max(LCS(x[0...xi],y[0...yj-1]), LCS(x[0...xi-1],y[0...yj]))

Answer 2

long max_sub(int i, int j)
{

    if(i<0 or j<0)
        return 0;

    if(s[i]==p[j])
    {
        if(dp[i][j]==-1)
          dp[i][j]=1+max_sub(i-1,j-1);
    }
    else
    {
        dp[i][j] = 0;
    }
    if(i-1>=0 and dp[i-1][j]==-1)
        max_sub(i-1, j);
    if(j-1>=0 and dp[i][j-1]==-1)
        max_sub(i, j-1);
    return dp[i][j];
}

你的代码的问题似乎是你没有尝试所有n ^ 2的可能性。

Answer 3

包algo.dynamic;

public class LongestCommonSubstring {

public static void main(String[] args) {
    String a = "LABFQDB";
    String b = "LABDB";
    int maxLcs = lcs(a.toCharArray(), b.toCharArray(), a.length(), b.length(), 0);
    System.out.println(maxLcs);
}

private static int lcs(char[] a, char[] b, int i, int j, int count) {
    if (i == 0 || j == 0)
        return count;
    if (a[i - 1] == b[j - 1]) {
        count = lcs(a, b, i - 1, j - 1, count + 1);
    }
    count = Math.max(count, Math.max(lcs(a, b, i, j - 1, 0), lcs(a, b, i - 1, j, 0)));
    return count;
}

}

Answer 4

我在c ++中为此设计了一个递归解决方案。在我的方法中我采取一个特定的i，j，然后如果他们是相等的我加1并调用函数为i + 1，j + 1，而如果他们不相等我在相应的i存储零，j在我创建的2D数组中。执行后我打印2D数组，似乎没问题。因为我只是填充2D数组，我认为时间复杂度必须是O（mn），其中m是一个数组的长度，n是另一个数组。

//Finding longestcommonsubword using top down approach [memoization]
#include<iostream>
using namespace std;

int findlength(char A[], char B[], int i, int j, int st[][5], int r, int c){

if(r <= i)
  return 0;
else if(c <= j)
  return 0;
else{
    if(A[i] == B[j]){

        if(st[i][j] == -1)
        st[i][j] = 1+findlength(A, B, i+1, j+1, st, r, c);
    }else{
        st[i][j] = 0;
        int a = findlength(A, B, i, j+1, st, r, c);
        int b = findlength(A, B, i+1, j, st, r, c);
    }
}    

return st[i][j];
}

int main(){
int n,m;
cin>>n>>m;
char A[n],B[m];

for(int i = 0;i < n;i++)
  cin>>A[i];

for(int j = 0;j < m;j++)
  cin>>B[j];

int st[n][5];


for(int k = 0; k < n;k++){
    for(int l = 0; l< 5;l++){
       st[k][l] = -1;   
    }
}
findlength(A, B, 0, 0, st, n, 5);

for(int k = 0; k < n;k++){
    for(int l = 0; l< 5;l++){
      cout<<st[k][l]<<" ";
    }
    cout<<endl;
}

return 0;
}