给定一个字符串s,生成一组所有唯一子串的最快方法是什么？
示例:因为str = "aba"我们会得到substrs={"a", "b", "ab", "ba", "aba"}.
朴素算法将遍历1..n每个迭代中生成长度的子串的整个字符串,产生O(n^2)上限.
更好的约束可能吗？
(这是技术上的功课,所以也欢迎指针)
目前我使用两个嵌套for循环来生成字符串的所有子字符串.我听说过,Suffix Tree但AFAIK Suffix Tree生成的后缀不是子串.以下是我目前使用的代码 -
String s = "abacbccca";
int l = s.length();
for (short c = 0; c < l; c++) {
for (short r = 0; r < l - c; r++){
Sting ss=s.substring(c, c + r + 1);
if(!t.contains(ss));
t.add(ss);
}
}
我想要一种能够生成所有子串的方法O(n^2).虽然通过查看我的代码,任何人都可以建议我这是不可能的,因为我将每个子字符串添加到列表中.但我的目标不是存储所有的子串,我的目标是找到一个字典,字典是字符串.
我有一个后缀数组SA和一个数组L,它存储两个连续后缀之间的LCP长度(最长公共前缀),即
L[i]=LCP(SA[i-1],SA[i]) where 1<=i<=|SA|
它也在这里描述.
我应该如何使用此数组L来找到给定的两个后缀x和y之间的LCP(x,y)？