在Java中后缀数组实现

我正在寻找一个有效的n阶马尔可夫链方法来生成给定一组示例文本的随机文本字符串。我目前有一个使用几层地图的Java实现，但它很笨拙。后缀数组对于我的需求来说是完美的，但我不清楚它是否可以在Java中有效地实现。在Java中后缀数组实现

在C我可能会做这样的事情：

char exampleText[MAX]; 
char *suffixArray[MAX]; 
... 
while(n<MAX && suffixArray[n++] = &exampleText[n]); 
sort(suffixArray);

这在Java中变得粗糙，因为我不得不采取的exampleText子，或转成suffixArray指数的数组，或别的东西。

有关在Java中使用此方法的任何建议吗？

来源

2010-07-28 Rich

String将[通常]为您做到这一点。（当与substring创建典型实现共享背衬阵列，尽管这是可能随时发生变化。）

来源

2010-07-28 04:22:33

谢谢你，我还没有想过尝试一下出。我只是假设它会爆炸。 – Rich 2010-07-28 14:36:52

不再。自从Java 7开始执行复制以来，所以最好编写自己的包装器 – 2013-09-30 09:13:35

任何有兴趣在构建在Java中后缀数组的更有效的方法，我曾经使用的库称为jsuffixarrays。代码是here。它提供了一系列可供选择的构造算法，我发现它工作得很好。例如。要使用SKEW算法，请执行以下操作：

import org.jsuffixarrays.Algorithm; 
import org.jsuffixarrays.ISuffixArrayBuilder; 
import org.jsuffixarrays.SuffixArrays; 
import org.jsuffixarrays.SuffixData; 

String    exampleText = "...."; 
ISuffixArrayBuilder suxBuilder = Algorithm.SKEW.getDecoratedInstance(); 
SuffixData   sux   = SuffixArrays.createWithLCP(text,sux_builder); 

/* Then, to access the suffix array: */ 
sux.getSuffixArray(); 
/* And, to access the LCP array: */ 
sux.getLCP();

如果不需要，可以不使用LCP阵列进行构建。

来源

2012-02-25 02:35:24 jogojapan

你可以做一些变种形式的后缀数组：

第一：

public static String[] suffixes(String s) 
{ 
int N = s.length(); 
String[] suffixes = new String[N]; 
for (int i = 0; i < N; i++) 
suffixes[i] = s.substring(i, N); 
return suffixes; 
}

二：

public static String[] suffixes(String s) 
{ 
int N = s.length(); 
StringBuilder sb = new StringBuilder(s); 
String[] suffixes = new String[N]; 
for (int i = 0; i < N; i++) 
suffixes[i] = sb.substring(i, N); 
return suffixes; 
}

来源

2013-04-16 11:16:56

在Java中后缀数组实现

回答

相关问题