可能重複:
How to find all substrings of a string in PHP
Find all subsets of a list計算所有給定的字符串的可能子串
我如何可以計算一個字符串的所有可能的子?例如給出一個字符串ABCDE。其所有可能的子串會
A, B, C, d, E, AB,BC , CD, DE, ABC, BCD, CDE, ABCD, BCDE , ABCDE
謝謝!僞代碼將受到高度讚賞。 :d
可能重複:
How to find all substrings of a string in PHP
Find all subsets of a list計算所有給定的字符串的可能子串
我如何可以計算一個字符串的所有可能的子?例如給出一個字符串ABCDE。其所有可能的子串會
A, B, C, d, E, AB,BC , CD, DE, ABC, BCD, CDE, ABCD, BCDE , ABCDE
謝謝!僞代碼將受到高度讚賞。 :d
只需使用兩個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 ""
你可能要包括空字符串""
在您返回的序列也是,因爲它是所有字符串的子字符串。
您還需要考慮多次產生重複字符串是否有效(例如,您是否作爲「ABABA」的子字符串返回兩次「ABA」?)。如果答案是否定的,那麼只需製作一個名爲alreadyYielded
的哈希表,並且每當您產生時,如果已經產生了字符串,則中止,否則將值添加到散列表中以防萬一您再次看到它。例如:
seen = new HashTable()
...
substring = string[...]
if substring not in seen:
seen.add(substring)
yield substring
...
謝謝@ninjagecko!順便說一句,如何計算這種子串的數量?正如在上面的例子中給出的,我有5個字符。 P(5)= 15,如上所示。我想知道函數P來計算一個字符串中所有可能的子字符串的數量。謝謝。 :D – neilmarion
它應該是2^n,因爲它與找到一組子集數量相同的問題 –
它不是2^n @ÓscarLópez,因爲2^5不是15.:P – neilmarion
這裏有一個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;
這種類型的問題已經被問了很多次才:http://stackoverflow.com/questions/728972,HTTP://計算器。 com/questions/1592039,http://stackoverflow.com/questions/5023081/,http://stackoverflow.com/questions/6780935/等等。只要搜索「powerset」或「子集」。 – bobbymcr
好的。我會關閉這個。 – neilmarion
我不同意肯和bobbymcr。儘管鏈接的問題確實是「如何找到一個字符串的子字符串?」它似乎涉及一些沉重的PHP和最少的解釋,就像答案一樣。所有鏈接bobbymcr鏈接是完全分開的問題,雖然相關(子串不是子集)。經過粗略的檢查,我找不到一個類似的語言不可知的問題,並用僞代碼給出了明確的答案。 – ninjagecko