logo标签列表

最长公共子串：递归解法？

stringalgorithmrecursiondynamic-programming
13

最长公共子串算法：

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，而i应该是3？

有人能指定一个递归解决方案吗？

14个回答
22

请尽量避免混淆，你所询问的是最长公共子字符串，而不是最长公共子序列，它们非常相似但是有所不同。

The recursive method for finding longest common substring is:
Given A and B as two strings, let m as the last index for A, n as the last index for B.

    if A[m] == B[n] increase the result by 1.
    if A[m] != B[n] :
      compare with A[m -1] and B[n] or
      compare with A[m] and B[n -1] 
    with result reset to 0.
以下是未应用记忆化的示例代码，以更好地说明算法。
   public int lcs(int[] A, int[] B, int m, int n, int res) {
        if (m == -1 || n == -1) {
            return res;
        }
        if (A[m] == B[n]) {
            res = lcs(A, B, m - 1, n - 1, res + 1);
        }
        return max(res, max(lcs(A, B, m, n - 1, 0), lcs(A, B, m - 1, n, 0)));
    }

    public int longestCommonSubString(int[] A, int[] B) {
        return lcs(A, B, A.length - 1, B.length - 1, 0);
    }
2
我们如何为其添加记忆功能。 - Neeraj Jain
在所有的解决方案中，人们都是从两个字符串的末尾开始吗？ 为什么我们不能从字符串的开头开始迭代？ - Rupesh
@Rupesh，你可以这样做，但基本情况会有所不同。 - user1234
这个解决方案属于最长公共子序列问题，而不是最长公共子串。原始问题也与最长公共子序列有关。 - albin
@albin 这不是最长公共子序列。实际上，这是最长公共子串的正确解决方案。 - Ketan R
2

这里是最长公共子串的递归代码：

int LCS(string str1, string str2, int n, int m, int count)
{
    if (n==0 || m==0)
        return count;
    if (str1[n-1] == str2[m-1])
        return LCS(str1, str2, n-1, m-1, count+1);
    return max(count, max(LCS(str1, str2, n-1, m, 0), LCS(str1, str2, n, m-1, 0)));
}
1

包算法.动态规划;

公共类 最长公共子串 {

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;
}

}

1
这是我对最长公共子串问题的递归解决方案。
ans = 0
def solve(i,j,s1,s2,n,m,dp):
    global ans

    # i is the starting index for s1
    # j is the starting index for s2

    if(i >= n or j >= m):
        return 0

    if(dp[i][j] != -1):
        return dp[i][j]
    

    if(s1[i] == s2[j]):
        dp[i][j] = 1 + solve(i+1,j+1,s1,s2,n,m,dp)

    else:
        dp[i][j] = 0

    solve(i,j+1,s1,s2,n,m,dp)
    solve(i+1,j,s1,s2,n,m,dp)
    ans = max(ans,dp[i][j]) # ans is storing maximum till now

    return dp[i][j]

def longestCommonSubstr(s1, s2, n, m):
    global ans
    # n is the length of s1
    # m is the length s2
    dp = [[-1 for i in range(m)] for j in range(n)]
    ans= 0
    solve(0,0,s1,s2,n,m,dp)
    return ans
0

我在C++中设计了一个递归解决方案。在我的方法中，我选择特定的i和j，如果它们相等，我就加1并调用i+1、j+1的函数，而如果它们不相等，我就在我创建的二维数组中对应的i、j处存储0。执行完后，我打印出这个二维数组，看起来没问题。由于我只是填充二维数组，所以时间复杂度应该是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;
}
0
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种可能性。

0

以下是计算最长公共字符串的递归方法：

public int lcsLength(String x, String y)
{
    char[] xc = x.toCharArray();
    char[] yc = y.toCharArray();

    return lcsLength(xc, xc.length - 1, yc, yc.length - 1, 0);
}

private int lcsLength(char[] xc, int xn, char[] yc, int yn, int currentCsLength)
{
    if (xn < 0 || yn < 0) {
        return currentCsLength;
    }
    if (xc[xn] == yc[yn]) {
        return lcsLength(xc, xn - 1, yc, yn - 1, currentCsLength + 1);
    }
    else {
        return max(currentCsLength,
                max(
                        lcsLength(xc, xn - 1, yc, yn, 0),
                        lcsLength(xc, xn, yc, yn - 1, 0)));
    }
}

使用此解决方案的缺点是，针对x和y的相同子字符串多次重新计算常见字符串，这会导致效率降低。
该解决方案使用记忆化技术 （memoization）来避免在递归中多次计算最长公共字符串。
public int lcsLength(String x, String y)
{
    char[] xc = x.toCharArray();
    char[] yc = y.toCharArray();

    Integer[][] memoization = new Integer[xc.length][yc.length];

    return lcsLength(xc, xc.length - 1, yc, yc.length - 1, memoization);
}

private int lcsLength(char[] xc, int xn, char[] yc, int yn, Integer[][] memoization)
{
    if (xn < 0 || yn < 0) {
        return 0;
    }
    if (memoization[xn][yn] == null) {
        if (xc[xn] == yc[yn]) {
            // find out how long this common subsequence is
            int i = xn - 1, j = yn - 1, length = 1;
            while (i >= 0 && j >= 0 && xc[i] == yc[j]) {
                i--;
                j--;
                length++;
            }
            memoization[xn][yn] = Math.max(length, lcsLength(xc, xn - length, yc, yn - length, memoization));
        }
        else {
            memoization[xn][yn] = max(
                    lcsLength(xc, xn - 1, yc, yn, memoization),
                    lcsLength(xc, xn, yc, yn - 1, memoization));
        }
    }

    return memoization[xn][yn];
}
0
     int max; //This gloabal variable stores max substring length
     int[][]dp; // 2D Array for Memoization

     void main(){
     //--------Main method just intended to demonstrate initialization---------

     dp = new int[m+1][n+1] //m and n are string length
     lcs(String a,String b,int n,int m)
     }
     
     //---++++++++-----Recrsive Memoized Function------++++++++++++-------
     static int lcs(String a,String b,int n,int m){
     
     if(dp[n][m]!=-1)return dp[n][m];
    
     if(n==0||m==0)return dp[n][m]=0;
     
     
     if(a.charAt(n-1)==b.charAt(m-1))
     {
        int res=0;int i=n-1,j=m-1;
        while((i>=0&&j>=0)&&a.charAt(i)==b.charAt(j)){
            res++;
            if(i==0||j==0)return dp[n][m] = Math.max(res,max);
            i--;j--;
        }
        max=Math.max(res,max);
        
        return dp[n][m]=Math.max(max,Math.max(lcs(a,b,n-res,m),lcs(a,b,n,m-res)));
         
     }
     
     return dp[n][m]=Math.max(lcs(a,b,n-1,m),lcs(a,b,n,m-1));
     
     
     
 }
0

递归+记忆化解决方案；发现所有可能的组合

class Solution{
    int[][] t;
    int longestCommonSubstr(String s1, String s2, int n, int m){
        // code here
        t = new int[n+1][m+1];
        for(int i = 0; i <=n; i++){
            for(int j = 0; j <=m; j++){
                t[i][j] = -1;
            }
        }
        for(int i = 0; i<=n; i++){
            t[i][0] = 0;
        }
        for(int j = 0; j<=m; j++){
            t[0][j] = 0;
        }
        solve(s1,s2,n,m);
        // for(int i = 0; i <=n; i++){
        //     for(int j = 0; j <=m; j++){
        //         System.out.print(t[i][j]+" ");
        //     }
        //     System.out.println();
        // }
        int ans = Integer.MIN_VALUE;
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <=m; j++){
                ans = Math.max(ans,t[i][j]);
            }
        }
        return ans;
    }
    
    private int solve(String s1, String s2, int m, int n){
        if(m == 0 || n == 0) return 0;
        int ans = 0;
        if(s1.charAt(m-1) == s2.charAt(n-1)){
            if(t[m][n] == -1){
                t[m][n] = 1 + solve(s1,s2,m-1,n-1);
            }
            ans = t[m][n];
        }
        if(t[m-1][n] == -1)
        t[m-1][n] = solve(s1,s2,m-1,n);
        if(t[m][n-1] == -1)
        t[m][n-1] = solve(s1,s2,m,n-1);
        return ans;

    }
}
0
希望这可以帮到你，尽管已经有很多答案了！
 public static int LongestCommonSubString(String x, String y, int m, int n, int curr_max) {
        if (m == 0 || n == 0) return curr_max;

        if (x.charAt(m - 1) == y.charAt(n - 1)) return LongestCommonSubString(x, y, m - 1, n - 1, curr_max + 1);
        
        return Math.max(LongestCommonSubString(x, y, m - 1, n, 0), LongestCommonSubString(x, y, m, n - 1, 0));
    }
1
你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心找到有关如何编写良好答案的更多信息。 - Community
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接