大矩陣中最大的相等子矩陣

假設您有一個高度h和寬度w的矩陣（h，w < = 500）您必須找到兩個相同大小相等的子矩陣。任何想法解決？大矩陣中最大的相等子矩陣

2014-03-19 user3333971

等於意味着子矩陣中的每個元素都相同？ – taocp

矩陣中元素的類型如何？這些數字或可以是字符/字符串？ – Mohan

子矩陣應該最大嗎？如果沒有，這很容易，你可以檢查是否有兩個元素具有相同的項目。 –

可以枚舉所有矢量（-h < DH <小時，0 < = DW<瓦特）在O（HW）。對於每個這樣的矢量，通過矢量（dh，dw）來轉換矩陣並從原始矩陣中減去轉換後的矩陣。在它們重疊的範圍內，您想要查找具有最大面積的零的矩形。您可以使用a linear time algorithm來做到這一點。

運行：O（w^^ h ）

一種更務實的方法是哈希所有子矩陣和重複檢查的方式。這將具有相同的預期運行時間。

來源

2014-03-19 00:58:12

h，w <= 500，O（w²h²）會花費太長時間，不是嗎（至少對於編程競賽標準來說）？ –

@JuanLopes：我不知道，根據我的估計，它可能會在一分鐘內運行。在比賽中，這肯定會太慢，但也許它不是那種問題 –

我沒有看到很多像「高度h和寬度w（h，w <= 500）」外部比賽的陳述：P –

存在比O更好的算法（w h ）。首先考慮一個更簡單的版本。給定一個只有小寫字母的矩陣M，找到矩陣中的最大子字符串。這個問題等於找到longest common substring在M[0]$1M[1]...M[w-1]，我們在M[i]和M[i+1]之間添加不同的特殊字符。使用suffix array，最長的公共子串問題可以在線性時間內解決，對於這種情況，它可以用O（wh）來解決。

對於最大子矩陣的問題，通過列舉所有可能的高度升< = H，在同一時間它可以是減少了的子問題，詞典順序2子帶高度l可以由具有高度的子串的順序繼承l-1。

正如@Niklas B解釋。在第一次迭代中，我們使用後綴數組來排列矩陣的行後綴。然後在第二步中，我們使用基數排序並重新使用第一次迭代中計算出的等級來排列相鄰2行組合的後綴。在第三步中，我們對相鄰3行的後綴進行排序等等。我們還可以爲每次迭代維護LCP arrays，這樣我們就可以使用一次遍歷找到出現兩次的最長子字符串。

總的來說，這個算法是ø（H 2 瓦特）與線性時間後綴數組構造算法。

來源

2014-03-19 03:04:19

對不起，我可憐的英語，你能理解第一部分嗎？ –

是的，我開始看到第二段的含義，但有點難理解。 –

我現在明白了。非常酷的想法，但是真的很難從你的答案中理解：/ –

大矩陣中最大的相等子矩陣

回答

相關問題