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

Question

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

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

谢谢！伪代码将不胜感激。：D

- neilmarion

---

这种类型的问题已经被问了很多次：https://dev59.com/yXRB5IYBdhLWcg3wET1J，http://stackoverflow.com/questions/1592039，http://stackoverflow.com/questions/5023081/，http://stackoverflow.com/questions/6780935/等等。只需搜索“powerset”或“subset”即可。 - bobbymcr

我不同意Ken和bobbymcr的观点。虽然这个链接问题是“如何找到字符串的子串？”，但它似乎涉及一些繁琐的PHP，解释很少，答案也是如此。bobbymcr提供的所有链接都是完全不同的问题，尽管相关（子串不是子集）。经过粗略检查，我找不到类似的与语言无关的问题，并且给出了清晰的伪代码答案。 - ninjagecko

@ninjagecko：第二次阅读后，我认为你是对的——原帖似乎想要比纯子集更专业化的东西，但类似于具有完全连接元素的子字符串（例如从ABC -> AB和BC，但不是AC）。 - bobbymcr

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
...

- ninjagecko

---

谢谢@ninjagecko！顺便问一下，如何计算这样的子字符串数量？如上例所示，我有5个字符。P(5) = 15，如上所示。我想知道函数P以获取字符串所有可能子字符串的计算。谢谢。 :D - neilmarion

应该是2^n，因为这与找到一个集合的所有子集的数量相同。 - Óscar López

这不是2的n次方，@ÓscarLópez，因为2的5次方不是15。 :P - neilmarion

我的错误，子字符串的数量与其字符序列的幂集不同！ - Óscar López

neilmarion：如果你看第二个循环返回的字符串数量，它看起来像这样：LENGTH+(LENGTH-1)+(LENGTH-2)+...+1，这等于LENGTH*(LENGTH+1)/2。 - ninjagecko

Answer 2

这里是一个简短的回答：

for (indexOfFirstLetterOfString = 0; indexOfFirstLetterOfString < string.length; indexOfFirstLetterOfString++) {

   for (indexOfLastLetterOfString = indexOfFirstLetterOfString + 1; indexOfLastLetterOfString < string.length; indexOfLastLetterOfString++) {

        addToArrayOfStrings ( string.substring (indexOfFirstLetterOfString, indexOfLastLetterOfString - indexOfFirstLetterOfString))
        incrementCounter();

    }
}

要得到组合数，只需在内部循环中加入计数器。

例如，在perl中，可以这样写：

$a = "ABCDE";

$numberOfSubstrings = 0;

for ($indexOfFirstLetter = 0; $indexOfFirstLetter <= length($a); $indexOfFirstLetter++) {

    for ($indexOfLastLetter = $indexOfFirstLetter + 1; $indexOfLastLetter <= length($a); $indexOfLastLetter++)  {
        print substr($a, $indexOfFirstLetter, $indexOfLastLetter - $indexOfFirstLetter) . "\n";

        $numberOfSubStrings++;
    }
}

print "Number of substrings: " . $numberOfSubStrings;

- Mike Fahy