确定现有字符串的所有子字符串的最快方法

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是三元