suffix-array

0熱度

2回答

查找最長重複子串的算法公式如下 1)build the suffix tree 2)find the deepest internal node with at least k leaf children 但我不明白爲什麼這個工作正常，所以基本上是什麼讓這個算法正確？還有，我發現這個算法說，在O（n）中找到重複的子字符串，其中n是子字符串的長度，這對我也不是很清楚！讓我們考慮下面的樹，這裏最長的重

0熱度

1回答

使用後綴數組搜索後綴

我已經構造了一個由ArrayList實現的後綴數組。我想用這個列表在後綴數組中搜索後綴。爲此，我已經整理了列表並使用二進制搜索，但「搜索」功能不斷返回-1 我不知道我在做什麼錯在這裏。我已經重寫了Hashcode並且也等於。我也改變了「等於」默認定義，但我還是繼續得到同樣的輸出 import java.util.ArrayList; import java.util.Collections;

1熱度

1回答

瞭解執行DC3/Skew算法以創建後綴數組線性時間

我想了解Karkkainen，P. Sanders的線性時間後綴數組創建算法的實現。算法的細節可以找到here。我設法理解整體概念，但未能與提供的實現相匹配，因此無法清楚地理解它。這裏是最初的代碼路徑令我困惑。作爲每紙：N0，N1，N2表示三聯體編號開始在爲i mod 3 =（0,1,2）由於每個代碼：N0 =（N + 2）/ 3中，n1 = （n + 1）/ 3，n2 = n/3; =>

0熱度

1回答

大數據集的廣義後綴樹Java實現

我有大約5000萬個字符串的集合，每個字符串都有大約100個字符。我正在尋找非常高效（運行時間和內存使用情況）的通用後綴樹實現。我已經試過https://github.com/npgall/concurrent-trees但它需要大量的內存事件，儘管運行時間很有效率。 250萬字符串的長度爲100.它已經花費了50GB的內存。

1熱度

2回答

什麼是後綴自動機？

有人可以請我解釋一下後綴自動機究竟是什麼，它是如何工作的，與後綴樹和後綴數組有什麼不同？我已經嘗試過在網上搜索，但無法找到任何明確的全面解釋。我發現下面的鏈接最接近我想要的，但它是在俄羅斯和翻譯到英語很難理解。 http://e-maxx.ru/algo/suffix_automata

0熱度

1回答

如何實現後綴數組c

然而，由於在算法頭文件中內置了Sort()函數，因此它很容易獲得使用C++的實現。我已經經歷了天真的方法和O（nlogn）形成數組的方法。在這兩種情況下，sort()函數都用於排序後綴。 C有沒有什麼好的方法？

1熱度

3回答

Python識別字符串集內的後綴

在CheckIO上做練習，我想知道爲什麼這不起作用。給定一組字符串，如果任何字符串是集合中任何其他字符串的後綴，我試圖返回True。否則爲假。使用itertools我首先在元組中生成必要的排列。然後，對於每個元組（每個元素），如果第二個元組位於第一個元組的末尾（選項1），我希望看到困難的方式。另一方面是使用.endwith函數（選項2），但都不適合我。爲什麼這兩個選項有缺陷？ import ite

1熱度

1回答

後綴數組實現錯誤

我一直收到編譯器錯誤，執行後綴數組Arrays.sort。我收到以下錯誤：一個不能被解析爲一個變量語法錯誤令牌「」。預計語法錯誤令牌「 - 」， - 預期一個不能被解析爲一個變量 B不能被解析爲一個變量在下面的代碼： import java.util.*; public class SuffixArray { // sort suffixes of S in O(n*l

3熱度

1回答

從後綴數組獲取LCP的代碼如何工作？

有人可以解釋如何從後綴數組構造LCP的代碼工作？ suffixArr[]是一個數組，使得suffixArr[i]在後綴字符串中保留索引值，該後綴的排名爲i。 void LCPconstruct() { int i,C[1001],l; C[suffixArr[0]] = n; for(i=1;i<n;i++) C[suffixArr[i]] = suf

4熱度

4回答

後綴數組開始使用scala

今天我試圖用scala創建後綴數組。我能夠用大量的代碼完成它，但後來我聽說它可以通過使用壓縮和排序只使用幾行來創建。我現在的問題是與開始。我嘗試使用二進制搜索和zipWithIndex來創建以下「樹」，但到目前爲止我還沒有能夠創建任何東西。我甚至不知道只用一條線是否可能，但我敢打賭它是大聲笑。我想要做的就是從一個字「芝士蛋糕」中獲得一個序列： Seq((cheesecake, 0),