计算给定字符串的所有可能的子字符串

Question

可能重复:
如何在PHP中查找字符串的所有子字符串
查找列表的所有子集

如何计算字符串的所有可能子串？例如给出一个字符串ABCDE.所有可能的子串都将是

A,B,C,D,E,AB,BC,CD,DE,ABC,BCD,CDE,ABCD,BCDE,ABCDE

谢谢!伪代码将受到高度赞赏.:d

Answer 1

只需使用两个for循环:

generate substrings(string):
    for start in [0,1,...,string.length-1]:
        for end in [start,...,string.length-1]:
            yield string[start...end]

你也可以用两个for循环这样做:

generate substrings(string):
    for substringLength in [1,2,...,string.length]:
        for start in range [0,1,...,string.length-substringLength]:
            yield string[start...(start+substringLength-1)]
    yield ""

您可能希望""在返回的序列中包含空字符串,因为它是所有字符串的子字符串.

您还需要考虑多次产生重复字符串是否有效(例如,您是否将"ABA"作为"ABABA"的子字符串返回两次？).如果答案是否定的,只需要调用一个哈希表alreadyYielded,并且每当你产生时,如果你已经产生了字符串,则中止,否则将值添加到哈希表中以防再次看到它.例如:

seen = new HashTable()
...
        substring = string[...]
        if substring not in seen:
            seen.add(substring)
            yield substring
...