src/Match.php
public function bitap($text, $pattern, $loc)
    {
        if ($this->getMaxBits() != 0 && $this->getMaxBits() < mb_strlen($pattern)) {
            throw new \RangeException('Pattern too long for this application.');
        }

        // Initialise the alphabet.
        $s = $this->alphabet($pattern);

        $patternLen = mb_strlen($pattern);
        $textLen = mb_strlen($text);

        // Highest score beyond which we give up.
        $scoreThreshold = $this->getThreshold();
        // Is there a nearby exact match? (speedup)
        $bestLoc = mb_strpos($text, $pattern, $loc);

        if ($bestLoc !== false) {
            $scoreThreshold = min($this->bitapScore(0, $bestLoc, $patternLen, $loc), $scoreThreshold);
            // What about in the other direction? (speedup)
            $bestLoc = mb_strrpos($text,$pattern, $loc + $patternLen);
            if ($bestLoc !== false) {
                $scoreThreshold = min($this->bitapScore(0, $bestLoc, $patternLen, $loc), $scoreThreshold);
            }
        }

        // Initialise the bit arrays.
        $matchMask = 1 << ($patternLen - 1);
        $bestLoc = -1;

        $binMax = $patternLen + $textLen;
        $lastRd = null;
        for ($d = 0; $d < $patternLen; $d++) {
            // Scan for the best match each iteration allows for one more error.
            // Run a binary search to determine how far from 'loc' we can stray at
            // this error level.
            $binMin = 0;
            $binMid = $binMax;
            while ($binMin < $binMid) {
                if ($this->bitapScore($d, $loc + $binMid, $patternLen, $loc) <= $scoreThreshold) {
                    $binMin = $binMid;
                } else {
                    $binMax = $binMid;
                }
                $binMid = (int)(($binMax - $binMin) / 2) + $binMin;
            }
            // Use the result from this iteration as the maximum for the next.
            $binMax = $binMid;
            $start = max(1, $loc - $binMid + 1);
            $finish = min($loc + $binMid, $textLen) + $patternLen;

            $rd = array_fill(0, $finish + 2, 0);
            $rd[$finish + 1] = (1 << $d) - 1;
            for ($j = $finish; $j > $start - 1; $j--) {
                if ($textLen <= $j - 1) {
                    // Out of range.
                    $charMatch = 0;
                } else {
                    $charMatch = isset($s[$text[$j - 1]]) ? $s[$text[$j - 1]] : 0;
                }
                if ($d == 0) {
                    // First pass: exact match.
                    $rd[$j] = (($rd[$j + 1] << 1) | 1) & $charMatch;
                } else {
                    // Subsequent passes: fuzzy match.
                    $rd[$j] = ((($rd[$j + 1] << 1) | 1) & $charMatch) |
                        ((($lastRd[$j + 1] | $lastRd[$j]) << 1) | 1) |
                        $lastRd[$j + 1];
                }
                if ($rd[$j] & $matchMask) {
                    $score = $this->bitapScore($d, $j - 1, $patternLen, $loc);
                    // This match will almost certainly be better than any existing match.
                    // But check anyway.
                    if ($score <= $scoreThreshold) {
                        // Told you so.
                        $scoreThreshold = $score;
                        $bestLoc = $j - 1;
                        if ($bestLoc > $loc) {
                            // When passing loc, don't exceed our current distance from loc.
                            $start = max(1, 2 * $loc - $bestLoc);
                        } else {
                            // Already passed loc, downhill from here on in.
                            break;
                        }
                    }
                }
            }
            // No hope for a (better) match at greater error levels.
            if ($this->bitapScore($d + 1, $loc, $patternLen, $loc) > $scoreThreshold) {
                break;
            }
            $lastRd = $rd;
        }
        return $bestLoc;
    }
public function bitap($text, $pattern, $loc)
    {
        if ($this->getMaxBits() != 0 && $this->getMaxBits() < mb_strlen($pattern)) {
            throw new \RangeException('Pattern too long for this application.');
        }

        // Initialise the alphabet.
        $s = $this->alphabet($pattern);

        $patternLen = mb_strlen($pattern);
        $textLen = mb_strlen($text);

        // Highest score beyond which we give up.
        $scoreThreshold = $this->getThreshold();
        // Is there a nearby exact match? (speedup)
        $bestLoc = mb_strpos($text, $pattern, $loc);

        if ($bestLoc !== false) {
            $scoreThreshold = min($this->bitapScore(0, $bestLoc, $patternLen, $loc), $scoreThreshold);
            // What about in the other direction? (speedup)
            $bestLoc = mb_strrpos($text,$pattern, $loc + $patternLen);
            if ($bestLoc !== false) {
                $scoreThreshold = min($this->bitapScore(0, $bestLoc, $patternLen, $loc), $scoreThreshold);
            }
        }

        // Initialise the bit arrays.
        $matchMask = 1 << ($patternLen - 1);
        $bestLoc = -1;

        $binMax = $patternLen + $textLen;
        $lastRd = null;
        for ($d = 0; $d < $patternLen; $d++) {
            // Scan for the best match each iteration allows for one more error.
            // Run a binary search to determine how far from 'loc' we can stray at
            // this error level.
            $binMin = 0;
            $binMid = $binMax;
            while ($binMin < $binMid) {
                if ($this->bitapScore($d, $loc + $binMid, $patternLen, $loc) <= $scoreThreshold) {
                    $binMin = $binMid;
                } else {
                    $binMax = $binMid;
                }
                $binMid = (int)(($binMax - $binMin) / 2) + $binMin;
            }
            // Use the result from this iteration as the maximum for the next.
            $binMax = $binMid;
            $start = max(1, $loc - $binMid + 1);
            $finish = min($loc + $binMid, $textLen) + $patternLen;

            $rd = array_fill(0, $finish + 2, 0);
            $rd[$finish + 1] = (1 << $d) - 1;
            for ($j = $finish; $j > $start - 1; $j--) {
                if ($textLen <= $j - 1) {
                    // Out of range.
                    $charMatch = 0;
                } else {
                    $charMatch = isset($s[$text[$j - 1]]) ? $s[$text[$j - 1]] : 0;
                }
                if ($d == 0) {
                    // First pass: exact match.
                    $rd[$j] = (($rd[$j + 1] << 1) | 1) & $charMatch;
                } else {
                    // Subsequent passes: fuzzy match.
                    $rd[$j] = ((($rd[$j + 1] << 1) | 1) & $charMatch) |
                        ((($lastRd[$j + 1] | $lastRd[$j]) << 1) | 1) |
                        $lastRd[$j + 1];
                }
                if ($rd[$j] & $matchMask) {
                    $score = $this->bitapScore($d, $j - 1, $patternLen, $loc);
                    // This match will almost certainly be better than any existing match.
                    // But check anyway.
                    if ($score <= $scoreThreshold) {
                        // Told you so.
                        $scoreThreshold = $score;
                        $bestLoc = $j - 1;
                        if ($bestLoc > $loc) {
                            // When passing loc, don't exceed our current distance from loc.
                            $start = max(1, 2 * $loc - $bestLoc);
                        } else {
                            // Already passed loc, downhill from here on in.
                            break;
                        }
                    }
                }
            }
            // No hope for a (better) match at greater error levels.
            if ($this->bitapScore($d + 1, $loc, $patternLen, $loc) > $scoreThreshold) {
                break;
            }
            $lastRd = $rd;
        }
        return $bestLoc;
    }
Locate the best instance of 'pattern' in 'text' near 'loc' using the
Bitap algorithm.

@param string $text    The text to search.
@param string $pattern The pattern to search for.
@param int    $loc     The location to search around.

@throws \RangeException If pattern longer than number of bits in int.
@return int Best match index or -1.