Calculation of all possible substrings of a given string

Question

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

How can I calculate all possible substrings of a string? For example, for the string ABCDE. All possible substrings will be

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

Thanks! Pseudocode will be highly appreciated .: D

Answer 1

Just use two for-loops:

generate substrings(string): for start in [0,1,...,string.length-1]: for end in [start,...,string.length-1]: yield string[start...end] 

You can also do this with two for-loops:

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

You probably want to include the empty string "" in the returned sequence, since it is a substring of all strings.

You also need to consider whether repeating a repeating string is permissible several times (for example, do you return "ABA" twice as a substring of "ABABA"?). If the answer is no, just create a hash table called alreadyYielded , and whenever you give in, abort if you already gave a row, otherwise add a value to the hash table if you see it again. For instance:

 seen = new HashTable() ... substring = string[...] if substring not in seen: seen.add(substring) yield substring ... 

Answer 2

Here is a 2 percent answer:

 for (indexOfFirstLetterOfString = 0; indexOfFirstLetterOfString < string.length; indexOfFirstLetterOfString++) { for (indexOfLastLetterOfString = indexOfFirstLetterOfString + 1; indexOfLastLetterOfString < string.length; indexOfLastLetterOfString++) { addToArrayOfStrings ( string.substring (indexOfFirstLetterOfString, indexOfLastLetterOfString - indexOfFirstLetterOfString)) incrementCounter(); } } 

To get the number of combinations, just add a counter to the inner loop.

For example, in perl, it might look like this:

 $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;