在字符串中搜索模式

Question

Pattern search within a string.

for eg.

$string = "111111110000";
FindOut($string);

Function should return 0

function FindOut($str){    
    $items =  str_split($str, 3);    
    print_r($items);
}

Answer 1

What you have here can conceptually be solved with a sliding window. For your example, you have a sliding window of size 3.

For each character in the string, you take the substring of the current character and the next two characters as the current pattern. You then slide the window up one position, and check if the remainder of the string has what the current pattern contains. If it does, you return the current index. If not, you repeat.

Example:

1010101101
|-|

So, pattern = 101. Now, we advance the sliding window by one character:

1010101101
 |-|

And see if the rest of the string has 101, checking every combination of 3 characters.

Conceptually, this should be all you need to solve this problem.

Edit: I really don't like when people just ask for code, but since this seemed to be an interesting problem, here is my implementation of the above algorithm, which allows for the window size to vary (instead of being fixed at 3, the function is only briefly tested and omits obvious error checking):

function findPattern( $str, $window_size = 3) {
    // Start the index at 0 (beginning of the string)
    $i = 0;

    // while( (the current pattern in the window) is not empty / false)
    while( ($current_pattern = substr( $str, $i, $window_size)) != false) {
        $possible_matches = array();

        // Get the combination of all possible matches from the remainder of the string
        for( $j = 0; $j < $window_size; $j++) {
            $possible_matches = array_merge( $possible_matches, str_split( substr( $str, $i + 1 + $j), $window_size));
        }

        // If the current pattern is in the possible matches, we found a duplicate, return the index of the first occurrence
        if( in_array( $current_pattern, $possible_matches)) {
            return $i;
        }

        // Otherwise, increment $i and grab a new window
        $i++;
    }
    // No duplicates were found, return -1
    return -1;
}

It should be noted that this certainly isn't the most efficient algorithm or implementation, but it should help clarify the problem and give a straightforward example on how to solve it.