String Searching Algorithms in PHP

Lesson Overview

Welcome to this insightful lesson. Today's focus will be on string searching algorithms, a fundamental part of programming often encountered in software development, the design of databases, and information retrieval. This lesson will walk you through the intricacies of these algorithms, explaining the principles behind each one.

Quick Example

For instance, consider the KMP string searching algorithm focusing on searching the given pattern inside the text as a substring, where the essence of its design is to eliminate the need to backtrack by retaining the information elicited from previous comparisons. If, at some point in the pattern, there's a mismatch, the algorithm does not begin matching the pattern with the text from the start but from a pre-computed point that takes into account all previous comparisons. It's an efficient way to avoid redoing work!

There are many details regarding this algorithm, but here is what its implementation might look like in PHP:

<?php
class KMPAlgorithm {
    public static function kmpSearch($text, $pattern) {
        $lps = self::computeLPSArray($pattern);
        $i = 0; // index for text
        $j = 0; // index for pattern
        $textLength = strlen($text);
        $patternLength = strlen($pattern);
        
        while ($i < $textLength) {
            if ($pattern[$j] === $text[$i]) {
                $i++;
                $j++;
            }
            if ($j == $patternLength) {
                return $i - $j;
            } elseif ($i < $textLength && $pattern[$j] !== $text[$i]) {
                if ($j != 0) {
                    $j = $lps[$j - 1];
                } else {
                    $i++;
                }
            }
        }
        return -1;
    }

    private static function computeLPSArray($pattern) {
        $length = 0;
        $i = 1;
        $patternLength = strlen($pattern);
        $lps = array_fill(0, $patternLength, 0);
        $lps[0] = 0; // lps[0] is always 0

        while ($i < $patternLength) {
            if ($pattern[$i] === $pattern[$length]) {
                $length++;
                $lps[$i] = $length;
                $i++;
            } else {
                if ($length != 0) {
                    $length = $lps[$length - 1];
                } else {
                    $lps[$i] = 0;
                    $i++;
                }
            }
        }
        return $lps;
    }
}

// Example usage
$text = "abxabcabcaby";
$pattern = "abcaby";
$result = KMPAlgorithm::kmpSearch($text, $pattern);
echo $result;  // Output: 6
?>

Feel free to ask questions to clarify the details!

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal