Java中的字符串子串生成

问题描述：

我正在尝试查找给定字符串中的所有子字符串。对于像rymis这样的随机字符串，子序列将是[i, is, m, mi, mis, r, ry, rym, rymi, rymis, s, y, ym, ymi, ymis]。从Wikipedia开始，长度为n的字符串将总共具有n * (n + 1)/2个子字符串。Java中的字符串子串生成

这可以通过执行下面的代码片段中找到：

final Set<String> substring_set = new TreeSet<String>(); 
    final String text = "rymis"; 

    for(int iter = 0; iter < text.length(); iter++) 
    { 
     for(int ator = 1; ator <= text.length() - iter; ator++) 
     { 
      substring_set.add(text.substring(iter, iter + ator)); 
     } 
    }

这对于小字符串长度的作品，但明显放缓的大长度的算法是近O(n^2)。

也阅读后缀树，它可以在O(n)插入，并注意到相同的子序列可以通过从右边删除1个字符重复插入子字符串直到字符串为空来获得。这应该是关于O(1 + … + (n-1) + n)这是一个summation of n - >n(n+1)/2 - >(n^2 + n)/ 2，这又是接近O(n^2)。虽然似乎有一些后缀树可以在log2(n)时间插入，这将是一个更好的因素O(n log2(n))。

在我深入研究后缀树之前，这是一条正确的路线，是否有另一种算法对此更有效率，或者是O(n^2)就好了？

这功课吗？ – 2012-02-22 19:12:54

由于该集合包含n *（n + 1）/ 2个值，因此您必须对该集合执行n *（n + 1）/ 2个插入操作，所以我没有看到算法如何小于O （N^2）。 – 2012-02-22 19:15:10

@JBNizet - 我同意，没有办法避免触及每个子串元素。由于原始集合的大小为n，并且大约有n^2个元素要访问，所以最有可能无法提高效率。 – 2012-02-22 19:28:14

答

这是你的例子的倒置方式，但仍然o（n^2）。

string s = "rymis"; 
ArrayList<string> al = new ArrayList<string>(); 
for(int i = 1; i < s.length(); i++){//collect substrings of length i 
for(int k = 0; k < s.length(); k++){//start index for sbstr len i 
    if(i + k > s.length())break;//if the sbstr len i runs over end of s move on 
    al.add(s.substring(k, k + i));//add sbstr len i at index k to al 
} 
}

让我看看我是否可以发布一个递归的例子。我开始做了几次递归尝试，并提出了使用双滑动窗口作为对上述方法的一种改进的这种迭代方法。我有一个递归的例子，但有问题减少树的大小。

string s = "rymis"; 
ArrayList<string> al = new ArrayList<string>(); 
for(int i = 1; i < s.length() + 1; i ++) 
{ 
for(int k = 0; k < s.length(); k++) 
{ 
    int a = k;//left bound window 1 
    int b = k + i;//right bound window 1 
    int c = s.length() - 1 - k - i;//left bound window 2 
    int d = s.length() - 1 - k;//right bound window 2 
    al.add(s.substring(a,b));//add window 1 
    if(a < c)al.add(s.substring(c,d));//add window 2 
} 
}

有一个问题提到使用数组列表影响性能，所以下一个将会更基本的结构。

string s = "rymis"; 
StringBuilder sb = new StringBuilder(); 
for(int i = 1; i < s.length() + 1; i ++) 
{ 
for(int k = 0; k < s.length(); k++) 
{ 
    int a = k;//left bound window 1 
    int b = k + i;//right bound window 1 
    int c = s.length() - 1 - k - i;//left bound window 2 
    int d = s.length() - 1 - k;//right bound window 2 
    if(i > 1 && k > 0)sb.append(","); 
    sb.append(s.substring(a,b));//add window 1 
    if(a < c){ 
    sb.append(","); 
    sb.append(s.substring(c,d));//add window 2 
    } 
} 
} 
string s = sb.toString(); 
String[] sArray = s.split("\\,");

答

我相当肯定你不能击败O（n^2），因为这已经在问题的评论中提到过了。

我对不同的编码方式感兴趣，所以我很快做出了一个决定，并且我决定在这里发布它。

我在这里提出的解决方案不是渐近地快，我不认为，但是当计算内部和外部循环的时候少了。这里也没有重复的插入 - 没有重复的插入。

String str = "rymis"; 
ArrayList<String> subs = new ArrayList<String>(); 
while (str.length() > 0) { 
    subs.add(str); 
    for (int i=1;i<str.length();i++) { 
     subs.add(str.substring(i)); 
     subs.add(str.substring(0,i)); 
    } 
    str = str.substring(1, Math.max(str.length()-1, 1)); 
}

答

我不知道确切的算法，但你可以看看绳索：

http://en.wikipedia.org/wiki/Rope_(computer_science)

综上所述，钢丝绳更适合当数据量较大，并经常修改。

我相信绳子胜过你的问题的字符串。

Java中的字符串子串生成

相关推荐