不同子串的拼接

Question

問題 - 按照字典順序排列給定字符串的所有不同子字符串並連接它們。打印連接字符串的第K個字符。可以肯定的是，給定的K值將是有效的，即將有第K個字符

輸入格式 第一行將包含數字T即測試用例的數量。 每個測試用例的第一行包含一個包含字符串的字符（A-Z）和第二線將包含許多K.

輸出格式 打印第K個字符（串1索引）

約束 1≤T≤5 1≤length≤105 K將是一個適當的整數。

採樣輸入＃00

1 
dbac 
3 

樣本輸出＃00

c 

說明＃00

的子串佈置在詞典順序時如下

一個，交流，b，ba，bac，c，d，db，dba，dbac 關於concate給他們，我們得到

aacbbabaccddbdbadbac 這個字符串中的第三個字符是c，因此答案。

這是我的代碼：

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 

public class Solution 
{ 

public static void gen(String str,int k) 
{ 


     int i,c;ArrayList<String>al=new ArrayList<String>(); 
    for(c=0;c<str.length();c++) 
    { 
     for(i=1;i<=str.length()-c;i++) 
     { 
      String sub = str.substring(c,c+i); 
      al.add(sub); 
     } 
    } 

    HashSet hs = new HashSet(); 
    hs.addAll(al); 
    al.clear(); 
    al.addAll(hs); 

    String[] res = al.toArray(new String[al.size()]); 
    Arrays.sort(res); 

    StringBuilder sb= new StringBuilder(); 

     for(String temp:res) 
     { 
      sb.append(temp); 
     } 

    String s = sb.toString(); 
    System.out.println(s.charAt(k-1)); 
} 


public static void main(String[] args) 
{ 
    Scanner sc = new Scanner (System.in); 
    int t = Integer.parseInt(sc.nextLine()); 

     while((t--)>0) 
     { 
      String str = sc.nextLine(); 
      int k = Integer.parseInt(sc.nextLine());     
      gen(str,k); 

     } 

    } 
} 

此代碼工作的很好像上面的測試情況下投入較小，但對大輸入的其超時或顯示這樣的事情我明白這個問題是與記憶，任何替代方法來做這個問題或反正重複使用相同的內存？

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space 
at java.util.Arrays.copyOfRange(Arrays.java:2694) 
at java.lang.String.<init>(String.java:203) 
at java.lang.String.substring(String.java:1913) 
at Solution.gen(Solution.java:19) 
at Solution.main(Solution.java:54) 

Answer 1

在給出的約束條件下（最多105個字符），你不應該有內存不足的問題。也許你正在用非常大的字符串進行測試。

所以，如果你有，這裏有一些地方，你是在浪費內存：

• 您填寫的設置後，你把它複製到你的列表中。這意味着子串集合的兩個副本，而你不打算再使用這個集合。
• 將列表複製到數組後，您現在有三個子串集合的副本，儘管您不打算再使用該列表。
• 現在您創建一個StringBuilder並將所有子字符串放入其中。但瞭解整個串聯字符串並不是很有趣。我們只需要一個字符，那爲什麼要把這個連接放在內存中呢？另外，在上面所有浪費的副本中，至少你沒有複製子字符串本身。但是現在您將它們追加到StringBuilder，您正在創建它們的副本。這將是一個非常長的字符串。
• 然後通過使用toString()將StringBuilder的內容複製到新字符串中。這創建了一個非常大的連接字符串的副本（我們已經說過我們並不需要它）。

您已經有了一個使用TreeSet並直接填充它的合理建議，而不是創建列表，集合和排序列表。下一步是從該集合中提取正確的字符，而實際上並未將連接字符串保留在左右。

因此，假設您的集合稱爲set：

Iterator<String> iter = set.iterator(); 

int lengthSoFar = 0; 
String str = null; 

while (lengthSoFar < k && iter.hasNext()) { 

    str = iter.next();   // Got the next substring; 
    lengthSoFar += str.length(); 
} 

// At this point we have the substring where we expect the k'th 
// character to be. 

System.out.println(str.charAt(k - lengthSoFar + str.length() - 1); 

注意，這將需要程序更長的時間才能到達的k比低值高值，但通常會比建築串聯整個快字符串，因爲只要你得到正確的子字符串，你就會停下來。

Answer 2

您的內存不足。您可以通過使用-Xms256m -Xmx1024啓動JVM來增加JVM使用的內存，並且可以嘗試一些優化。

public static void gen(String str, int k) { 

    int i, c; 

    //Adding directly to the Set prevents a larger list because you remove the duplicates 
    Set<String> set = new TreeSet<String>(); 

    for (c = 0; c < str.length(); c++) { 
     for (i = 1; i <= str.length() - c; i++) { 
      String sub = str.substring(c, c + i); 
      set.add(sub); 
     } 
    } 
    //TreeSet already orders by the String comparator 


    StringBuilder sb = new StringBuilder(); 

    for (String temp : set) { 
     sb.append(temp); 
     if(sb.length()>k){ 
      break; 
     } 
    } 

    String s = sb.toString(); 
    System.out.println(s.charAt(k - 1)); 
} 

[編輯]增加了小的性能提升。試着看看它是否變快，我沒有看StringBuilder.length（）的性能，看它是否會改善或減少。