數據結構

我們感興趣的是二進制字符串的數據結構。讓S = s s .... s _m是大小爲m的二進制字符串。 Shift(S,i)是字符串Si位向左循環移位。也就是說，移位（S，I）= S _我小號_{i + 1的}小號_{I + 2}內容S_米小號內容S _I-1。表明支持一個有效的數據結構：數據結構

爲O的empy DS的Init()（1）
Insert(s)插入在O二進制串到DS（| S |^2）
Search_cyclic(s)檢查是否O（| s |）中的任何i都有Shift(S,i)。

空間複雜度：O（| S 1 | + | S 2 | + ..... + | S_米 |）其中，S _我是一個如果米串我們已經插入了這麼多。

如果我必須找到Search_cyclic（S，I）對一些給我，這是與使用後綴樹，只是爲O穿越它很簡單（| S |）。但是在Search_cyclic中，我們沒有給定的i，所以我不知道在給定的複雜度下應該怎麼做。 OTOH，Insert通常將O（| s |）插入到後綴樹中，在這裏給出O（| s |^2）。

來源

2012-01-20 Jenny B

我認爲這是作業。如果不是這樣，請再次移除作業標籤。 –

| s |是什麼意思？包含二進制字符串的字符串的大小或DS的大小？ Search_cyclic檢查什麼？ – Shraddha

| s |是我們在Search_cyclic（s）中搜索的字符串的大小。 Search_cyclic（s）應檢查DS中是否存在字符串s的移位字符串。我認爲這個想法是使用後綴樹，我對Insert（s）有一些影響，它可以在O（| s |^2）中，而通常將字符串插入後綴樹只需要O（| s |）。所以我應該做一些聰明的事情，增加回旋餘地。 –

所以這裏是一個解決方案，我可以向你求婚。複雜程度比他們詢問你的要複雜得多，但看起來有點複雜。

保留所有字符串的數據結構將是Trie甚至Patricia tree。在這個樹中，每個字符串都要插入所有可能的移位中的最小循環移位（即循環移位所有可能的循環移位，這是最小的按字典順序排列）。您可以計算線性時間內字符串的最小循環移位，稍後我會給出一個可能的解決方案。現在讓我們假設你可以做到這一點。下面是所需的操作將如何實施：

的init（） - 初始化都特里和Patricia樹是不變的 - 在這裏沒有問題
插入（S） - 你計算的最小循環移位S'的s in O（| s |），然後將其插入到O（| s'|）= O（| s |）中的任一數據結構中。這是更好的，則需要複雜
Search_cyclic（S） - 您再計算爲O S的最小循環移位（| S |），然後你在帕特里夏或特里檢查字符串出現，這又是在O（| s |）中完成

此外，內存複雜度是根據需要的，如果構建Patricia可能會更低。

所以所有剩下的就是exaplain如何找到最小的循環移位。既然你提到後綴樹，我希望你知道如何在linear time中構建它。所以訣竅是 - 你將自己的字符串添加到自身中（即，加倍），然後爲雙倍字符串構造一個後綴樹。這對於| s |仍然是線性的所以沒有問題。之後，你所要做的就是在這棵樹中找到最小長度爲n的後綴。這並不難，我相信 - 從根開始，始終遵循當前節點上寫有最小字符串的鏈接，直到累積長度超過| s |。由於字符串翻倍，您將始終能夠遵循最小字符串鏈接，直到您至少累積長度爲| s |。

希望此回答有幫助。

來源

2012-01-23 07:57:46

回答

相關問題