允許有效提取塊的字符串數據結構？

Question

我正在尋找兩用陣列（如果有的話！）

例如

obj[1] = "Tea"; 
obj[2] = "Coffee"; 
obj[3] = "Cola"; 

數組應該以這樣的方式訪問，不管什麼每個字符串數組的長度，則結果應該pirnted出作爲

obj(5)(1) = "TeaCo" 
obj(5)(2) = "ffeeC" 
obj(5)(2) = "ola" 

我知道，我們可以寫，通過數組循環代碼，並打印出結果如上，但有一個數據結構，它可以直接做到這一點？

Answer 1

好像您的查詢的形式爲

如果輸入被分成大小爲k的塊，將第r塊是什麼呢？

讓我們調用這種查詢塊查詢（k，r）。

通過使用擴充平衡二叉樹，您可以在時間O（k + log n）中支持這些查詢，其中n是不同字符串的數目。使用左右子樹中的字符總數以及左右子樹中的字符串數量（換句話說，對順序統計樹進行變形）標註樹中的每個節點。此外，通過節點對雙鏈表進行線程化，以便可以在時間O（1）中從任何節點導航到其後繼者。

要在索引i處插入或更新值，請搜索與位置i對應的節點，並在其之前插入新值或更新其內容。

要執行塊查詢（k，r），請使用增強搜索索引爲kr的字符。這需要時間O（log n）。然後，在讀取k個字符之前，請繼續閱讀當前節點中的字符，並根據需要通過鏈接列表遍歷下一個節點。這需要花費時間O（k），如果節點中的平均字符數很少，可能會少很多。

希望這會有所幫助！

Answer 2

「有沒有可以直接做到的數據結構？」

是的。它是一個字符數組，也被稱爲字符串。

如果您的字符串是"TeaCoffeeCola"，那麼（在Java中），string.substring(0,5)是"TeaCo"。 string.substring(5,5)是"ffeeC"。等等。

無論您使用何種語言，您都可以輕鬆地爲自己編寫一個函數，從中抽取字符串中的一系列字符。這就是你所需要的。