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

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

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

回答

相关问题