如何區分C++中的兩個非常長的字符串？

我想解決 Levenshtein_distance這個問題，在字符串的長度過於龐大。如何區分C++中的兩個非常長的字符串？

EDIT2：
作爲Bobah說，標題是錯過領先，所以我必須更新questoin的稱號。
初始title was如何在C++中聲明100000x100000二維整數？
Content was
有任何方式來聲明INT X [100000] [100000]在C++中。
當我在全局聲明它時，編譯器生成error: size of array ‘x’ is too large。
一種方法可以使用map< pair< int , int > , int > mymap。
但分配和釋放需要更多時間。
還有其他方式可以使用uisng vector<int> myvec;

來源

2014-10-05 user3919801

機器上有40 GB內存嗎？因爲這就是數組的多少。 – interjay 2014-10-05 12:50:08

你知道你的陣列需要40或80 GB嗎？你有那麼多的RAM？ – deviantfan 2014-10-05 12:50:10

爲什麼你需要這麼大的陣列？ – P0W 2014-10-05 12:50:22

對於內存塊是大的，最好的辦法是使用操作系統的設施，增加虛擬內存的進程動態分配。

然而，看看你正在嘗試塊多大分配：

40 000 000 000 bytes

我把我以前的建議了。對於一個龐大的塊，最好的方法是分析問題並找出一種使用更少內存的方法。

來源

2014-10-05 12:51:22 user3344003

1TB RAM在服務器世界中已經成爲現實，但同意，差異不需要將所有內容加載到RAM中，除非它需要確定性到最後一點。 – bobah 2014-10-05 18:05:25

填充編輯距離矩陣可以一次完成每行。記住前一行足以計算當前行。這種觀察將空間使用從二次方減少到線性。說得通？

來源

2014-10-05 13:14:36 saadtaame

你的問題很有趣，但標題是誤導。

這是您在數據模型方面需要什麼（X - 第一個字符串，Y - 第二個字符串，* - 距離矩陣）。

 y <-- first string (scrolls from top down) 

     y 
    x x x x x x x x <- second string (scrolls from left to right) 
     y * * * 

     y * * * 

     y * * * <-- distance matrix (a donut) scrolls together with strings 
        and grows/shrinks when needed, as explained below 
     y

有兩臺相對長的（但仍然< < N）字符緩衝器和相對較小（< <緩衝器尺寸）的矩形距離矩陣（正方形從開始）。

使矩陣成爲一個donut - 二維環形緩衝區（可以使用boost中的一個，或者僅使用std :: deque）。

噹噹前由矩陣覆蓋串的片段是100％匹配由一個移位兩個緩衝器，旋轉兩軸周圍的圓環，重新計算一個新的行/在距離矩陣列。

如果匹配爲< 100％且小於配置的閾值，則增加甜甜圈的兩個維度的大小而不丟棄任何行/列，並執行此操作，直到任一匹配達到閾值以上或達到最大甜甜圈大小。當匹配率從下面達到閾值時，您需要滾動圓環丟棄x和y緩衝區的頭部，並同時對齊它們（當距離矩陣表明X [i]不存在於Y中時，只需要X移動1 ，但是X [i + 1，i + m]匹配Y [j，j + m-1]）。

因此，您將有確定性的有限的內存佔用一個簡單但非常有效的啓發式區別引擎，並在啓動時所有的內存可以預先分配所以沒有動態分配在運行時會慢下來。

Apache v2 license，以防你決定去找它。

來源

2014-10-05 17:49:02 bobah

這個算法的時間複雜度是多少？ – user3919801 2014-10-12 06:19:33

'k * O（N）'，'k'由配置參數定義，主要是「甜甜圈」的最大可能尺寸（越大越慢） – bobah 2014-10-12 11:34:40

如何區分C++中的兩個非常長的字符串？

回答

相關問題