確定現有字符串的所有子字符串的最快方法

Question

比方說，我有字符串"Hey"。我想確定此字符串中存在的字符的所有組合，儘可能快地使用快速。得到的算法應該產生這樣的：

H, e, y, He, ey, Hey 

，因爲它不字符串作爲一個子中存在的算法應該不產生串"Hy"。

Answer 1

還有那些子的O(n^2)，長度[1,n]的，所以任何算法生成個個將是O(n^2) * O(n) = O(n^3)：

（*）查看EDIT2末 - 取決於弦的實施 - 複雜性可以改變從O(n^2)到O(n^3)

僞代碼：

result <- {} #result is a set if dupes should be terminated, otherwise - it is a multiset. 
for i from 0 to s.length: 
    for j from i+1 to s.length: 
     result.add(s.substring(i,j)) 
return result 

不過請注意，TH你可以做一些「作弊」，通過創建一個迭代器和動態生成的字符串，它應該是這個樣子[僞代碼]：

class MyIterator: 
    String s 
    int i,j 
    MyIterator(String s): 
    this.s = s 
    i = 0 
    j = 0 
    next(): 
    j = j + 1 
    if (j >= s.length): 
    i = i + 1 
    j = i + 1 
    if (i >= s.length): 
     throw exception 
    return s.substring(i,j) 

注意，創建迭代器O(1)，並且每次迭代是O(n) - 但要真正生成所有元素，您需要O(n^2)步驟，因此複雜性總體上仍然爲O(n^3)，但您可以減少應用程序的延遲。

編輯：
我editted複雜，聲稱這是O(n^2)是錯誤的，複雜O(n^3)因爲你需要生成可變長度的字符串，其中有些是長。至少一半的生成的子串的將是長n/2的 - 因此總的複雜性爲Theta(n^3)

EDIT2：
在某些情況下，它實際上可以O(n^2) - 取決於字符串實現。在java中的例子 - 它使用一個單一的char[]，只有「中扮演」與offset和length - 所以在Java中 - 創作其實是O(n^2)，因爲創建一個字符串是O(1)
在C然而 - 這是O(n^3)，因爲每個子需要複製到不同的char[]。

Answer 2

在php中檢查n-gram的實現。

在您的例子字符串：嘿

H，E，Y是對unigram

HE，EY是二元語法

HEY是三元