How to find all substrings of a string in PHP

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

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

Minor correction to the second one:

<?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 - $i) + 1);    
    }   
}   
return $subs;
}

$subs = get_all_substrings("abc");
print_r($subs);

?>

Answer 4

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

Answer 5

All possible substrings

  <?php   
         $str1 = "ABCD";
         $len = strlen($str1);
         $arr = array();
         for($i = 0; $i < $len; $i++){  
             for($j = 0; $j < $len - $i; $j++){  
                 $arr [] = substr($str1,$i,($j+1));  
             }  
         }  

         echo(json_encode($arr));
     ?>

Answer 6

And this question will not be complete without the recursive answer:

function get_substrings($str){
    $len = strlen($str);
    $ans = array();
    $rest = array();
    for ($i = 1; $i <= $len; $i++) {                 
        $ans[] = substr($str, 0, $i);        
    }
    if($str){
        $rest = get_substrings(substr($str, 1));
    }
    return array_merge($ans, $rest);
}

$subs = get_substrings("abc");
print_r($subs);

Answer 7

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.

Answer 8

This works and it works also with multibyte strings, all the methods above don't, they return null and duplicated values.

function substrings($str, $charset = 'UTF-8') {   
  $length = mb_strlen($str, $charset);

  $subs = [];
  for ($i = 0; $i < $length; $i++)
    for ($j = 1; $j <= $length; $j++)
      $subs[] = mb_substr($str, $i, $j, $charset);

  return array_unique($subs);
}

print_r(substrings("php"));

Answer 9

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.