What is the fastest way to find the occurrence of a string in another string?

Question 1

Possible Duplicate:
Which method is preferred strstr or strpos ?

Hi!

Could you tell me which one is faster:
strstr($mystring, $findme);
OR
strpos($mystring, $findme);
OR
anything else
in finding the - first or any - occurrence of a string in another one?

Does it even matter in performance if I check the occurrence in a case-insensitive mode with stristr() OR stripos()?

In my case it doesn't matter in which exact position the given string is (if any), or how many times it occurs in the other one (if any), the only important question is if it even exists in the other string.

I've already found some comments about differences of speed in various articles (e.g. on php.net, someone says strstr() is faster in case there is a !== false check after strpos), but now I can't decide which is true.

If you know about any better methods of searching a string in another, please let me know!

Thank you very much for the relevant comments!

============

An example:


$mystring = 'blahblahblah';  
$findme = 'bla';  

if(strstr($mystring, $findme)){  
   echo 'got it';  
}  
else{  
   echo 'none';  
}  

echo PHP_EOL;

if(strpos($mystring, $findme) !== false){  
   echo 'got it';  
}  
else{  
   echo 'none';  
}

Question 2

strpos seems to be in the lead, I've tested it with finding some strings in 'The quick brown fox jumps over the lazy dog':

strstr used 0.48487210273743 seconds for 1000000 iterations finding 'quick'
strpos used 0.40836095809937 seconds for 1000000 iterations finding 'quick'
strstr used 0.45261287689209 seconds for 1000000 iterations finding 'dog'
strpos used 0.39890813827515 seconds for 1000000 iterations finding 'dog'

<?php

    $haystack = 'The quick brown fox jumps over the lazy dog';

    $needle = 'quick';

    $iter = 1000000;

    $start = microtime(true);
    for ($i = 0; $i < $iter; $i++) {
        strstr($haystack, $needle);
    }
    $duration = microtime(true) - $start;
    echo "<br/>strstr used $duration microseconds for $iter iterations finding 'quick' in 'The quick brown fox jumps over the lazy dog'";

    $start = microtime(true);
    for ($i = 0; $i < $iter; $i++) {
        strpos($haystack, $needle);
    }
    $duration = microtime(true) - $start;
    echo "<br/>strpos used $duration microseconds for $iter iterations finding 'quick' in 'The quick brown fox jumps over the lazy dog'";

    $needle = 'dog';

    $start = microtime(true);
    for ($i = 0; $i < $iter; $i++) {
        strstr($haystack, $needle);
    }
    $duration = microtime(true) - $start;
    echo "<br/>strstr used $duration microseconds for $iter iterations finding 'dog' in 'The quick brown fox jumps over the lazy dog'";

    $start = microtime(true);
    for ($i = 0; $i < $iter; $i++) {
        strpos($haystack, $needle);
    }
    $duration = microtime(true) - $start;
    echo "<br/>strpos used $duration microseconds for $iter iterations finding 'dog' in 'The quick brown fox jumps over the lazy dog'";

?>

Question 3

Update: I've found a better solution

I've never played with php's similar_text() function but I thought I'd give it a shot...

$array = explode(PHP_EOL,'Slim Aluminium HDMI Lead, 1m Blue
Slim Aluminium HDMI Lead, 2m Blue
Slim Aluminium HDMI Lead, 3m Blue
Frozen Kids Headphones with Volume Limiter
XLR Plug to Socket Lead, 3m
XLR Plug to Socket Lead, 6m
Monster High Kids Headphones with Volume Limiter
TMNT Kids Headphones with Volume Limiter
Batman Kids Headphones with Volume Limiter
1-Gang Cable Entry Brush Wall Plate White/White Brushes 50 x 45mm
2-Gang Cable Entry Brush Wall Plate White/White Brushes 50 x 100mm
1-Gang Cable Entry Brush Wall Plate White/Black Brushes 50 x 45mm
2-Gang Cable Entry Brush Wall Plate White/Black Brushes 50 x 100mm
Slim Aluminium HDMI Lead, 5m Blue
Slim Aluminium HDMI Lead, 7.5m Blue
6.35mm (1/4") Mono Jack to Jack Guitar Lead, 5m Orange
XLR Plug to Socket Lead, 0.5m
XLR Plug to Socket Lead, 1m
XLR Plug to Socket Lead, 2m');

$output = array();
while( empty( $array ) === false )
{
  $currentWord = array_shift( $array );
  $currentGroup = array( $currentWord );
  foreach( $array as $index => $word )
  {
    if( similar_text( $word, $currentWord, $percentage ) and $percentage > 80 )
    {
      $currentGroup[] = $word;
      unset( $array[ $index ] );
    }
  }
  $output[] = $currentGroup;
}

print_r($output);

// Array
// (
//     [0] => Array
//         (
//             [0] => Slim Aluminium HDMI Lead, 1m Blue
//             [1] => Slim Aluminium HDMI Lead, 2m Blue
//             [2] => Slim Aluminium HDMI Lead, 3m Blue
//             [3] => Slim Aluminium HDMI Lead, 5m Blue
//             [4] => Slim Aluminium HDMI Lead, 7.5m Blue
//         )
// 
//     [1] => Array
//         (
//             [0] => Frozen Kids Headphones with Volume Limiter
//             [1] => Monster High Kids Headphones with Volume Limiter
//             [2] => TMNT Kids Headphones with Volume Limiter
//             [3] => Batman Kids Headphones with Volume Limiter
//         )
// 
//     [2] => Array
//         (
//             [0] => XLR Plug to Socket Lead, 3m
//             [1] => XLR Plug to Socket Lead, 6m
//             [2] => XLR Plug to Socket Lead, 0.5m
//             [3] => XLR Plug to Socket Lead, 1m
//             [4] => XLR Plug to Socket Lead, 2m
//         )
// 
//     [3] => Array
//         (
//             [0] => 1-Gang Cable Entry Brush Wall Plate White/White Brushes 50 x 45mm
//             [1] => 2-Gang Cable Entry Brush Wall Plate White/White Brushes 50 x 100mm
//             [2] => 1-Gang Cable Entry Brush Wall Plate White/Black Brushes 50 x 45mm
//             [4] => 2-Gang Cable Entry Brush Wall Plate White/Black Brushes 50 x 100mm
//         )
// 
//     [4] => Array
//         (
//             [0] => 6.35mm (1/4") Mono Jack to Jack Guitar Lead, 5m Orange
//         )
// 
// )

Assoc array edit

$products = array(
  array('id'=>'A','name'=>'Slim Aluminium HDMI Lead, 1m Blue'),
  array('id'=>'B','name'=>'Slim Aluminium HDMI Lead, 2m Blue'),
  array('id'=>'C','name'=>'Slim Aluminium HDMI Lead, 3m Blue'),
  array('id'=>'D','name'=>'1-Gang Cable Entry Brush Wall Plate White/White Brushes 50 x 45mm'),
  array('id'=>'E','name'=>'2-Gang Cable Entry Brush Wall Plate White/White Brushes 50 x 100mm'),
  array('id'=>'F','name'=>'1-Gang Cable Entry Brush Wall Plate White/Black Brushes 50 x 45mm'),
  array('id'=>'G','name'=>'2-Gang Cable Entry Brush Wall Plate White/Black Brushes 50 x 100mm'),
  array('id'=>'H','name'=>'Slim Aluminium HDMI Lead, 5m Blue'),
  array('id'=>'I','name'=>'Slim Aluminium HDMI Lead, 7.5m Blue')
);
$output = array();
while( empty( $products) === false )
{
  $currentProduct = array_shift( $products );
  $currentGroup = array( $currentProduct );
  foreach( $products as $index => $product )
  {
    if( similar_text( $product['name'], $currentProduct['name'], $percentage ) and $percentage > 80 )
    {
      $currentGroup[] = $product;
      unset( $products[ $index ] );
    }
  }
  $output[] = $currentGroup;
}
print_r($output);

Question 4

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

Question 5

You can concatenate using an embedded 'set' statement in a query:

declare @combined varchar(2000)
select @combined = isnull(@combined + ', ','') + isnull(value,'')
from simpleTable

print @combined

(Note that the first isnull() initialises the string, and the second isnull() is especially important if there's any chance of nulls in the 'value' column, because otherwise a single null could wipe out the whole concatenation)

(edited code and explanation after comments)

Edit (ten years later):

SQL Server 2017 introduced the STRING_AGG() function which provides an official way of concatenating strings from different rows. Like other aggregation functions such as COUNT(), it can be used with GROUP BY.

So for the example above you could do:

select string_agg(value, ', ')
from simpleTable

If you had some other column and you wanted to concatenate for values of that column, you would add a 'group by' clause, e.g:

select someCategory, string_agg(value, ', ') as concatValues
from simpleTable
group by someCategory

Note string_agg will only work with SQL 2017 and above.

Question 6

Please see the comments interspersed with the code on how it works.

(* True if a has period p *)
testPeriod[p_, a_] := Drop[a, p] === Drop[a, -p]

(* are all the list elements the same? *)
homogeneousQ[list_List] := Length@Tally
=== 1
homogeneousQ[{}] := Throw[$Failed] (* yes, it's ugly to put this here ... *)

(* auxiliary for findPeriodOfFirstElement[] *)
reduce[a_] := Differences@Flatten@Position[a, First[a], {1}]

(* the first element occurs every ?th position ? *)
findPeriodOfFirstElement[a_] := Module[{nl},
  nl = NestWhileList[reduce, reduce[a], ! homogeneousQ[#] &];
  Fold[Total@Take[#2, #1] &, 1, Reverse[nl]]
  ]

(* the period must be a multiple of the period of the first element *)
period[a_] := Catch@With[{fp = findPeriodOfFirstElement[a]},
   Do[
    If[testPeriod[p, a], Return[p]],
    {p, fp, Quotient[Length[a], 2], fp}
    ]
   ]

Please ask if findPeriodOfFirstElement[] is not clear. I did this independently (for fun!), but now I see that the principle is the same as in Verbeia's solution, except the problem pointed out by Brett is fixed.

I was testing with

b = RandomInteger[100, {1000}];
a = Flatten[{ConstantArray[b, 1000], Take[b, 27]}];

(Note the low integer values: there will be lots of repeating elements within the same period *)

EDIT: According to Leonid's comment below, another 2-3x speedup (~2.4x on my machine) is possible by using a custom position function, compiled specifically for lists of integers:

(* Leonid's reduce[] *)

myPosition = Compile[
  {{lst, _Integer, 1}, {val, _Integer}}, 
  Module[{pos = Table[0, {Length[lst]}], i = 1, ctr = 0}, 
    For[i = 1, i <= Length[lst], i++, 
      If[lst[[i]] == val, pos[[++ctr]] = i]
    ]; 
    Take[pos, ctr]
  ], 
  CompilationTarget -> "C", RuntimeOptions -> "Speed"
]

reduce[a_] := Differences@myPosition[a, First[a]]

Compiling testPeriod gives a further ~20% speedup in a quick test, but I believe this will depend on the input data:

Clear[testPeriod]
testPeriod = 
 Compile[{{p, _Integer}, {a, _Integer, 1}}, 
  Drop[a, p] === Drop[a, -p]]

What is the fastest way to find the occurrence of a string in another string?

An example:

Answers

php,string,substring