編輯距離動態編程爲非常大的輸入

-2

我正在解決衆所周知的編輯距離動態編程問題。其實問題給出了兩個字符串string1和string2，並給予刪除，插入和替換字符的成本，我必須在DP中，我必須使用二維數組。對於一個小字符串（大小爲< = 10000），我的代碼正在工作，但對於更大的輸入（大小> = 100000），編譯器會說「數組大小太大「。如果問題必須使用動態編程來解決（對於輸入大小= 100000），那麼請告訴我應該如何處理這個錯誤。這裏是我的代碼。編輯距離動態編程爲非常大的輸入

#include <iostream> 
#include <cstdio> 
#include <stdlib.h> 
#include <algorithm> 
#include <map> 
#include <queue> 
#include <iomanip> 
#include <string> 
#include <math.h> 
#include <limits> 
#include <map> 
#include <float.h> 
#include <limits.h> 
#include <string.h> 
using namespace std; 
#define rep(i,a,N) for(int i=a;i<N;++i) 
int DP[10000][10000],delete_cost,add_cost,replace_cost; 
string first,second; 
int Min(int x,int y,int z){ 
    int min=x<y?x:y; 
    min=min<z?min:z; 
    return min; 
} 

int Transform(int i,int j){ 
    if(DP[i][j]!=-1){ 
     //printf("DP is set\n"); 
     return DP[i][j]; 
    } 
    if(i==first.size()) 
     return (second.size()-j)*add_cost; 
    if(j==second.size()) 
     return (first.size()-i)*delete_cost; 
    if(first.at(i)!=second.at(j)){ 
     int add,del,rep; 
     add=Transform(i,j+1)+add_cost; 
     del=Transform(i+1,j)+delete_cost; 
     rep=Transform(i+1,j+1)+replace_cost; 
     return DP[i][j]=Min(add,del,rep); 
    } 
    else 
     return DP[i][j]=Transform(i+1,j+1); 

} 
    int main(){ 
    int T,a,b,k,ans; 
    scanf("%d",&T); 

    while(T--){ 
     memset(DP,-1,sizeof(DP)); 
     cin>>first; 
     cin>>second; 
     scanf("%d %d %d",&a,&b,&k); 
     add_cost=a; 
     delete_cost=b; 
     replace_cost=k; 
     //ans=Transform(0,0); 
     //if(ans<=k) 
      printf("%d\n",ans); 
     //else 
     // printf("%d\n",-1); 
    } 
return 0; 
}

來源

2014-10-07 Aadil Ahmad

可能的重複[如何區分兩個非常長的字符串在c + +？]（http://stackoverflow.com/questions/26202686/how-to-differentiate-two-very-long-strings-in-c） – 2014-10-07 20:16:08

作爲建議副本中的答案之一（儘管我認爲這是一個更清晰的問題 - 也許應該用這個答案），如果你只是想要_distance_，你不需要完整的NxM矩陣;您只需要上一行/列，以便更新重複。事實證明，你也可以重建線性內存中的編輯，但這有點微妙。 – 2014-10-07 21:11:40

正確的，因爲你的100000 * 100000陣列的32位整數佔用的內存40 GB的。您需要使用不同的算法。如果您只需要計算編輯距離達到一定的最大值k，那麼經典算法的修改版本只使用O(n * (2k + 1))存儲（其中n是字符串長度），因爲它只使用動態編程的中間對角線2k + 1矩陣。

來源

2014-10-07 20:10:08 japreiss

您能否請您解釋一下算法或者給出一些對該算法的參考。 – 2014-10-08 03:13:33

編輯距離動態編程爲非常大的輸入

回答

相關問題