使用一維數組的LCS動態編程

我正在嘗試動態編程來查找LCS的長度。我已經使用了二維數組。但是對於一個很大的字符串，由於內存溢出而給出了運行時錯誤請告訴我如何在一維數組中執行此操作以避免內存限制。使用一維數組的LCS動態編程

#include<bits/stdc++.h> 
#include<string.h> 
using namespace std; 
int max(int a, int b); 
int lcs(string X, string Y, int m, int n) 
{ 
    int L[m+1][n+1]; 
    int i, j; 
    for (i=0; i<=m; i++) 
    { 
    for (j=0; j<=n; j++) 
    { 
     if (i == 0 || j == 0) 
     L[i][j] = 0; 

     else if (X[i-1] == Y[j-1]) 
     L[i][j] = L[i-1][j-1] + 1; 

     else 
     L[i][j] = max(L[i-1][j], L[i][j-1]); 
    } 
    } 

    return L[m][n]; 
} 

int max(int a, int b) 
{ 
    return (a > b)? a : b; 
} 

int main() 
{ 
    string X; 
    string Y; 
    cin>>X>>Y; 
    int m = X.size(); 
    int n = Y.size(); 

    printf("Length of LCS is %d\n", lcs(X, Y, m, n)); 

    return 0; 
}

來源

2016-03-17 Abhishek Dudhal

[OT]'int L [m + 1] [n + 1];'使用可變長度數組** **擴展**，更喜歡使用'std :: vector'。 – Jarod42

向量也給運行時錯誤輸入字符串500k左右 –

棘手;你可能需要修改[Hirshberg的算法]（https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm）來解決這個問題。這是可行的，但肯定比簡單的LCS算法複雜得多（編輯：啊，你只對長度感興趣，而不是實際的子序列;這很容易，見謝爾蓋的答案）。無關地，你*絕對*需要使用'vector'而不是可變長度的數組;還要打開編譯器警告（GCC和clang上的'-Wall -Wextra'），並讓你的編譯器迂迴（GCC和clang上的'-pedantic'）。 –

請注意，lcs中的遞歸僅使用L矩陣的最後兩行。因此，您可以輕鬆地重寫您的解決方案以使用O（N）內存。

這是關於這個問題的good article。

來源

2016-03-17 12:41:12

二維陣列是小說，無論如何，它仍然是一個維陣列，所以對自己的，即，計算的索引：讓你的陣列INT L [（N + 1）（M + 1）]和的索引L [i] [j] = L [i（n + 1）+ j]

來源

2016-03-17 12:40:37 jonezq

這不會解決二次內存問題。 –

正是它不會解決內存問題 –

使用一維數組的LCS動態編程

回答

相關問題