How to find all substrings of a string

Question

I need to convert strings of the form

"a b c"

into arrays of the form

Array
(
    [0] => a
    [1] => a b
    [2] => a b c
    [3] => b
    [4] => b c
    [5] => c
)

Does PHP provide a native function for converting strings into all substrings? If not, what's the path of least resistance for getting all substrings? Is there a straightforward way to perhaps explode() the string, and use an array op to generate all [ordered] permutations?

Cheers!

Answer 1

Substrings are not permutations. explode() the string, then use two nested loops along with array_slice() to get the relevant elements.

Answer 2

<?php
function get_all_substrings($input){
    $subs = array();
    $length = strlen($input);
    for($i=0; $i<$length; $i++){
        for($j=$i; $j<$length; $j++){
            $subs[] = substr($input, $i, $j);               
        }
    }
    return $subs;
}

$subs = get_all_substrings("Hello world!");
print_r($subs);

?>

Even if there's a fancy two-liner to accomplish this, I doubt it's any more efficient or easy to understand (for anybody to understand it they'd probably have to look at the docs. Most folks probably get what substr does without even looking it up).

Answer 3

Using the in-php-array-is-the-duct-tape-of-the-universe way :P

function get_all_substrings($input, $delim = '') {
    $arr = explode($delim, $input);
    $out = array();
    for ($i = 0; $i < count($arr); $i++) {
        for ($j = $i; $j < count($arr); $j++) {
            $out[] = implode($delim, array_slice($arr, $i, $j - $i + 1));
        }       
    }
    return $out;
}

$subs = get_all_substrings("a b c", " ");
print_r($subs);

Answer 4

For even quite short strings, the memory and runtime requirement will explode. Even in native code this is a scary performance problem.

Justify why you need this function, and work out another way around the problem.

Answer 5

They can already be thought of arrays of that form.

Simply address the contents with a function that takes the index as a parameter and returns the string sliced appropriately.