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

Question

Possible Duplicate:
How to find all substrings of a string in PHP
Find all subsets of a list

如何计算字符串的所有可能的子字符串？例如给定一个字符串 ABCDE。它所有可能的子串都是

一个， 乙， C， D、 乙， AB, 公元前， 光盘， 德, ABC, 二进制码， CDE, A B C D， 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
...