計算所有給定的字符串的可能子串

可能重複：
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

2011-11-29 neilmarion

這種類型的問題已經被問了很多次才：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

只需使用兩個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 
...

來源

2011-11-29 03:26:18 ninjagecko

謝謝@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;

來源

2011-11-29 03:34:34

計算所有給定的字符串的可能子串

回答

相關問題