Java中的字符串子串生成

Question

我正在嘗試查找給定字符串中的所有子字符串。對於像rymis這樣的隨機字符串，子序列將是[i, is, m, mi, mis, r, ry, rym, rymi, rymis, s, y, ym, ymi, ymis]。從Wikipedia開始，長度爲n的字符串將總共具有n * (n + 1)/2個子字符串。

這可以通過執行下面的代碼片段中找到：

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)就好了？

Answer 1

這是你的例子的倒置方式，但仍然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("\\,"); 

Answer 2

我相當肯定你不能擊敗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)); 
} 

Answer 3

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

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

綜上所述，鋼絲繩更適合當數據量較大，並經常修改。

我相信繩子勝過你的問題的字符串。