# Simple string-split by root and sufix algorithm

A classic problem to split a string into its "root and suffix":

There are many ways to implement the same algorithm, so, what is the best? Examples in PHP, but valid for any language.

/**
* Splits a string by its root and sufix.
* @param $str string input * @param$root string empty when no root, or start string
* @return array (rootFlag,sufix)
*/
function  str_splitByRoot($str,$root){
...
}


Algorithms str_splitByRoot1(), str_splitByRoot2(), ..., str_splitByRoot5() or other (show more if you know). All do the same thing, are valid solutions.

function  str_splitByRoot1($str,$root){
if (strpos($str,$root)===0)
return array($root, substr($str, strlen($root)) ); else return array( '',$str );
}

function  str_splitByRoot2($str,$root){
$rootLen = strspn($str ^ $root, "\0"); return array( substr($root,0,$rootLen), substr($str,$rootLen) ); } function str_splitByRoot3($str, $root){$s = explode($root,$str);
return ( count($s)>1 && !array_shift($s) )?
array($root,join($root,$s)): array('',$str);
}

function  str_splitByRoot4($str,$root){
// to generalize need a secure regex, something like
// $regex = str_replace(array('/','.','-'),array('\\/','\\.','\\-'),$root);
$suffix = preg_replace("/^$root/",$str,1,$n);
return $n? array($root,$suffix): array('',$str);
}

function  str_splitByRoot5($str,$root){
// need also $root translating as algorithm 4. if (preg_match("/^$root(.+)$/",$str,$m)) return array($root,$m[1]); else return array('',$str);
}


The first is the traditional way. The last (algorithms 4 and 5) use regular expression, the second trim excess garbage from strings that are null terminated; and the third remember that the algorithm is a kind of split (explode function).

All can be used with

function str_sepByRoot($str,$root){
return join(' * ',str_splitByRoot($str,$root));
}
print "\n".str_sepByRoot("walking","walk");
print "\n".str_sepByRoot("hello","walk");
print "\n".str_sepByRoot("walking-walk-walk","walk");
print "\n".str_sepByRoot("/var/www/myApp","/var/www/");
print "\n".str_sepByRoot("10.1038/ncomms7368","10.1038/ncomms");


returning

   walk * ing
* hello
walk * ing-walk-walk
/var/www/ * myApp
10.1038/ncomms * 7368


About "best thing"... The "principle of simplest is best" seems valid. The number of commands, and the computational simplicity of each command.

• str_splitByRoot1: 2 fast commands (strpos and substr) and 1 condition and strlen
• str_splitByRoot2: 2 fast commands (substr) and 1 to be checked (strspn+str ^ str)
• str_splitByRoot2 optimized: 1 fast command (substr), 1 to be checked (strspn) and 1 condition.
• ...

So, my doubt was about strspn+str ^ str performance... And its time struck me most, was near time for str_splitByRoot1...

  $str_splitByRoot = array( function ($str, $root){ // str_splitByRoot1() if (strpos($str,$root)===0) return array($root, substr($str, strlen($root)) );
else
return array( '', $str ); }, function ($str, $root){ //str_splitByRoot2()$rootLen = strspn($str ^$root, "\0");
return array( substr($root,0,$rootLen), substr($str,$rootLen) );
},
function  ($str,$root){ //str_splitByRoot2() optimized
$rootLen = strspn($str ^ $root, "\0"); return array($rootLen?$root:'' , substr($str,$rootLen) ); }, function ($str, $root){ //str_splitByRoot3()$s = explode($root,$str);
return ( count($s)>1 && !array_shift($s) )?
array($root,join($root,$s)): array('',$str);
}

function ($str,$root){ // str_splitByRoot5
$root2 = str_replace(array('/','.','-'),array('\\/','\\.','\\-'),$root);
if (preg_match("/^$root2(.+)$/",$str,$m))
return array($root,$m[1]);
else
return array('',$str); } ); function str_sepByRoot($i,$str,$root){
global $str_splitByRoot; global$debug;
$func =$str_splitByRoot[$i];$s = join(' * ', call_user_func($str_splitByRoot[$i],$str,$root)); // $func($str,$root)); if ($s &&  $debug) print "\n ___$s";
}

$debug=0; for ($i=0; $i<count($str_splitByRoot); $i++) { print "\n---$i ---";
$time = microtime(true); // time in Microseconds for($j=0;($j<333 && !$debug) || ($debug &&$j<1); $j++){ str_sepByRoot($i,"walking","walk");
str_sepByRoot($i,"hello","walk"); str_sepByRoot($i,"walking-walk-walk","walk");
str_sepByRoot($i,"/var/www/myApp","/var/www/"); str_sepByRoot($i,"DOI:10.1038/ncomms7368","DOI:10.1038/ncomms");
}
echo "\n", (microtime(true) - \$time) . ' elapsed';
}


Result:

--- 0 ---
0.0037140846252441 elapsed
--- 1 ---
0.0045409202575684 elapsed
--- 2 ---
0.0040040016174316 elapsed
--- 3 ---
0.0088369846343994 elapsed
--- 4 ---
0.0075829029083252 elapsed
--- 5 ---
0.0037930011749268 elapsed


Conclusion, using str_splitByRoot1 as reference (100%),

• str_splitByRoot2 optimized is ~105% , so for practical use it's as good as str_splitByRoot1.

• str_splitByRoot2 is ~115%, something good when compared with str_splitByRoot3 (~125%).

• str_splitByRoot5 is 225%... as expected, the worst (even without str_replace regex escapes).

... But, the performance changes (!) when using a big root, an Lorem ipsum of 800 words. The performance profile changed to:

• str_splitByRoot2 (optimized or not) ~244%... bad!

• str_splitByRoot3 (with direct split by explode) is ~120%, very good!

• str_splitByRoot5 (regex) ~390%, the worst of course.

So, the only that shows more "stability" (~120%) about root length was str_splitByRoot5, and str_splitByRoot2 is not a good replacement for str_splitByRoot1 in the context of big roots.