strpos() with multiple needles?

Asked 2011-08-01T09:38:41.713

I am looking for a function like strpos() with two significant differences:

To be able to accept multiple needles. I mean thousands of needles at ones.
To search for all occurrences of the needles in the haystack and to return an array of starting positions.

Of course it has to be an efficient solution not just a loop through every needle. I have searched through this forum and there were similar questions to this one, like:

but nether of them was what I am looking for. I am using strpos just to illustrate my question better, probably something entirely different has to be used for this purpose.

I am aware of Zend_Search_Lucene and I am interested if it can be used to achieve this and how (just the general idea)?

Thanks a lot for Your help and time!

Edit Report

2 Answers

Here's some sample code for my strategy:

function strpos_array($haystack, $needles, $offset=0) {
    $matches = array();

    //Avoid the obvious: when haystack or needles are empty, return no matches
    if(empty($needles) || empty($haystack)) {
        return $matches;
    }

    $haystack = (string)$haystack; //Pre-cast non-string haystacks
    $haylen = strlen($haystack);

    //Allow negative (from end of haystack) offsets
    if($offset < 0) {
        $offset += $heylen;
    }

    //Use strpos if there is no array or only one needle
    if(!is_array($needles)) {
        $needles = array($needles);
    }

    $needles = array_unique($needles); //Not necessary if you are sure all needles are unique

    //Precalculate needle lengths to save time
    foreach($needles as &$origNeedle) {
        $origNeedle = array((string)$origNeedle, strlen($origNeedle));
    }

    //Find matches
    for(; $offset < $haylen; $offset++) {
        foreach($needles as $needle) {
            list($needle, $length) = $needle;
            if($needle == substr($haystack, $offset, $length)) {
                $matches[] = $offset;
                break;
            }
        }
    }

    return($matches);
}

I've implemented a simple brute force method above that will work with any combination of needles and haystacks (not just words). For possibly faster algorithms check out:

Aho–Corasick string matching algorithm

Other Solution

function strpos_array($haystack, $needles, $theOffset=0) {
    $matches = array();

    if(empty($haystack) || empty($needles)) {
        return $matches;
    }

    $haylen = strlen($haystack);

    if($theOffset < 0) {  // Support negative offsets
        $theOffest += $haylen;
    }

    foreach($needles as $needle) {
        $needlelen = s


                        
                        
                            answered 2011-08-01T09:56:56.510


            
            
                
                    
                        
                            
                            
                        
                        0
                        
                            
                            
                        
                        
                    
                    
                        
                        You could use a regular expression, they support OR operations. This would however make it fairly slow, compared to strpos.

                        
                        
                            answered 2011-08-01T09:42:01.543



        
        
            Your Answer