找到一個字符串的所有不同的子串

你好傢伙我給了家庭作業問題，它要求我找到一個字符串的所有不同的子串。我已經實現了一個方法，它會告訴你所有的字符串的子字符串，但我需要一個幫助，弄清楚如何不計算一個已經被計數一次的子字符串，因爲分配是爲了找到不同的字符串。找到一個字符串的所有不同的子串

public int printSubstrings1(int length) 
{ 
    for(int i=0; i<text.length()-length+1;i++) 
    { 
     String sub = text.substring(i,length+i); 

     counter++; 
    } 
    return counter; 

}

這裏我傳遞了我想從te字符串給定的子字符串的長度。我正在通過另一種方法做到這一點。

所以給出的例子字符串是「fred」，而不同的子字符串將是10.我的方法將輸出正確的答案，因爲字符串不包含任何重複的字母。我被卡在我做重複子字符串的部分。

如果我輸入fred。這是我的方法將輸出

長度1
˚F
ř
Ë
d
長度2
FR
重新
編
長度3
FRE
紅色
長度4
fred

來源

2012-11-03 Dfsdfsdf Dsfsdfdsf

將它們放入[Set]（http://docs.oracle.com/javase/7/docs/api/java/util/Set.html） - 「Set是一個不包含重複元素的集合」 – jlordo

好主意謝謝你設置你的意思是陣列的權利。比如何檢查字符串是否已經存在。因爲陣列沒有。包含它的類中的方法。 –

http://stackoverflow.com/questions/5076099/avoid-duplicate-strings-in-java – Chris

將任何新的子字符串插入到數組中，並檢查它是否已經可用，並且不會將其添加到數組中。完成時，循環遍歷數組並打印出不同的子字符串。

若要檢查數組中是否存在元素，請創建一個將數組和值作爲參數的函數。如果找到返回值，它將遍歷數組尋找值。在循環之外返回false。

例如

public static boolean(String target, String[] arr) 
{ 
    for(int i = 0; i < arr.length; i++){ 
     if(arr[i].equals(target)) 
     return true; 
    } 
    return false; 
}

來源

2012-11-03 21:46:33

如果你的數組有未初始化的單元格，這將拋出'NullPointerException' – jlordo

這裏例如用Set

public int printSubstrings1(int length) { 
    Set<String> set = new HashSet<String>(); 
    for(int i=0; i < text.length() - length + 1; i++) { 
     String sub = text.substring(i,length+i); 
     set.add(sub); 
    } 
    for (String str : set) { 
     System.out.println(str); 
    } 
    return set.size(); 
}

來源

2012-11-03 21:46:42 jlordo

public ArrayList<String> getAllUniqueSubset(String str) { 
     ArrayList<String> set = new ArrayList<String>(); 
     for (int i = 0; i < str.length(); i++) { 
      for (int j = 0; j < str.length() - i; j++) { 
       String elem = str.substring(j, j + (i+1)); 
       if (!set.contains(elem)) { 
        set.add(elem); 
       } 
      } 
     } 
     return set; 
    }

來源

2014-06-23 17:51:40

如果你想添加一些註釋，你的答案會更有幫助 – 2014-06-23 18:08:12

本算法使用只是Z-功能/ Z算法。

對於單詞的每個前綴i，將其反轉並對其執行z_function。以i結尾的新的不同子字符串的數量是(the length of the prefix) — (maximum value in the z_function array)。的僞代碼如下所示：

string s; cin >> s; 
int sol = 0 
foreach i to s.size()-1 
    string x = s.substr(0 , i+1); 
    reverse(x.begin() , x.end()); 
    vector<int> z = z_function(x); 
    //this works too 
    //vector<int> z = prefix_functionx(x); 
    int mx = 0; 
    foreach j to x.size()-1 
     mx = max(mx , z[j]); 
    sol += (i+1) - mx; 

cout << sol;

該算法的時間複雜度是O（n^2）。最大值也可以從z_function返回。

Source.

這不是我原來的答覆。我只是鏈接到它並粘貼它，以防鏈接關閉。

來源

2017-01-17 02:04:20 user5735122

我跟着這個link。確認類似答案的內容在quora

解決方案包括構建後綴數組，然後根據最長公共前綴查找不同子字符串的數量。

一個關鍵這裏的觀察是：

如果你通過一個字符串的每一個後綴的前綴，你已經把這個字符串的所有子。

讓我們採取一個實例：香蕉

後綴是：0）香蕉1）阿納納2）NANA 3）ANA 4）NA 5）

這將是一個更容易經過前綴如果我們對上面的一組後綴進行排序，我們可以輕鬆地跳過重複的前綴。

有序集合後綴：5）A 3）ANA 1）阿納納0）香蕉4）NA 2）NANA

從現在開始，2串

LCP =最長公共前綴。

初始化

ANS =長度（第一後綴）=長度（「A」）= 1

現在考慮連續對後綴，即，[A，ANA]，[ANA，阿納納的]，[ANANA，BANANA]等，從上面的排序後綴集合中選擇。我們可以看到，LCP（「A」，「ANA」）=「A」。

不屬於公共前綴的所有字符都有助於產生不同的子字符串。在上述情況下，他們是'N'和'A'。所以他們應該被添加到ans。

因此，我們有，1個2 ANS + =長度（「ANA」） - LCP（「A」，「ANA」）ANS = ANS + 3 - 1 = ANS + 2 = 3

執行相同對於下一對連續的後綴：[「ANA」，「ANANA」]

1 2 3 4 LCP（「ANA」，「ANANA」）=「ANA」。 ANS + =長度（「阿納納」） - 長度（LCP）=> ANS = ANS + 5 - 3 => ANS = 3 + 2 = 5。

類似地，我們有：

1 2 LCP（（BANANA）= 0 ans = ans + length（「BANANA」） - 0 = 11

1 2 LCP（「BANANA」，「NA」）= 0 ans = ans + length（「NA 「） - 0 = 13

1 2 LCP（」 NA」，「NANA」）= 2 ANS = ANS +長度（「NANA」） - 2 = 15

因此不同的子串的數量字符串「BANANA」= 15。

來源

2017-08-10 17:12:12

找到一個字符串的所有不同的子串

回答

相關問題