兩個循環緩衝區是否相等？（雖然忽略轉變）

我有兩個循環緩衝區 - 我怎麼知道，如果一個只是另一個轉變？兩個循環緩衝區是否相等？（雖然忽略轉變）

例如B1 = 1,1,2,1,8,1,5,7，B2 = 2,1,8,1,5,7,1,1我們可以說B1和B2是相等的，因爲我可以旋轉其中的一個來獲得另一個。

測試這種相等性的最佳算法是什麼？明顯的測試是在O(n^2)（只比較緩衝區 - 在n步驟 - 從他們的每個n元素開始），但我相信我已經看到了線性時間算法。你能指點我嗎？

來源

2014-11-06 A123321

難道你不知道頭或兩個緩衝區的尾部？ – 2014-11-06 12:28:45

緩衝區中元素的數量是否相同？ – smk 2014-11-06 12:33:39

@smk如果他們不是，那麼只是一個簡單的大小比較就可以解決問題。我想我們很安全，以確保它們具有相同的尺寸。 – streppel 2014-11-06 12:37:43

假設B1和B2具有相同的長度，你的問題就相當於問：「是B2的B1 + B1一個子」（與自身串聯B1）。

例如：4元素字符串是1234的旋轉當且僅當它是12341234的子字符串。

檢查一個字符串是否是另一個字符串的子字符串可以使用KMP algorithm在線性時間內完成。

來源

2014-11-06 14:21:11 zch

Z算法也是另一種選擇，但可能更易於編碼和理解（對於某些人）。 – turingcomplete 2014-11-06 14:29:10

但仍然導致'O（n^2）'解決方案 – CaldasGSM 2014-11-06 15:59:50

@ CaldasGSM，怎麼樣？檢查長度 - 'O（1）'。複製字符串 - 'O（n）'，KMP/Z-算法 - 'O（2n）= O（n）'。 – zch 2014-11-06 16:02:59

如果你的緩衝區是整數，我想也許你可以使用添加作爲交換屬性(a+b == b+a) 這一事實，這意味着列表的開始並不重要。但另一方面請注意物品(1+2+3+4) = (3+1+2+4)的順序，以確保物品按照正確的順序排列，我們可以將它們成對或三重關聯。以更好地確保鏈接順序.. (12+23+34+41)或類似這樣的東西..

var B1 = [1,1,2,1,8,1,5,7] 
var B2 = [2,1,8,1,5,7,1,1] 
var B3 = [2,1,8,1,5,7,1,4] 

function checksum(buff) 
{ 
    var sum = 0 
    for(var i = 0 ; i < buff.length;i++) 
    { 
     var a = buff[i]; 
     var b = buff[(i+1)%buff.length]; 
     var c = buff[(i+2)%buff.length]; 
     var n = ((a*100) + (b * 10) + c); 
     sum += n; 
    } 
    return sum; 
} 
console.log(checksum(B1) == checksum(B2))//true 
console.log(checksum(B1) == checksum(B3))//false

這是一個「順序敏感」循環校驗

但像每一個散列函數會有碰撞和誤報，所以你會還需要比較的二次方法..

不知道如果我在正確的軌道上..希望有人能幫助更好地使或完全否定..

來源

2014-11-06 16:47:21 CaldasGSM

兩個循環緩衝區是否相等？ （雖然忽略轉變）

回答

相關問題

兩個循環緩衝區是否相等？（雖然忽略轉變）