PHP Program for Naive Algorithm for Pattern Searching

What is PHP?

PHP (Hypertext Preprocessor) is a widely used server-side scripting language for web development. It allows developers to embed code within HTML files, enabling the creation of dynamic web pages and interactions with databases. PHP is known for its simplicity, versatility, and extensive integration capabilities with popular databases. It offers a broad range of extensions and has a large community of developers, ensuring ample resources and support.

What is Naive Algorithm in PHP?

The Naive algorithm, also known as the Brute Force algorithm, is a simple pattern searching algorithm used to find occurrences of a pattern within a text. It is called "naive" because it does not employ any sophisticated data structures or advanced techniques.

In the context of PHP, the Naive algorithm is implemented as a function that takes in two parameters: the text to search within and the pattern to search for. The algorithm iterates through the text, comparing each character with the corresponding character in the pattern. If a mismatch is found, it moves to the next character in the text and starts the comparison again. If a match is found, it continues comparing subsequent characters until either the entire pattern is matched or a mismatch occurs.

PHP program for Naive Algorithm for Pattern Searching

Example

<?php
function searchPattern($text, $pattern)
{
   $textLength = strlen($text);
   $patternLength = strlen($pattern);

   $foundIndexes = array(); // Array to store the found indexes

   // Iterate through the text
   for ($i = 0; $i <= $textLength - $patternLength; $i++) {
      $j = 0;

      // Check for a match at the current position
      while ($j < $patternLength && $text[$i + $j] == $pattern[$j]) {
         $j++;
      }

      // If a match is found, add the starting index to the array
      if ($j == $patternLength) {
         $foundIndexes[] = $i;
      }
   }

   return $foundIndexes;
}

// Example usage
$text = "ABCABCABCABC";
$pattern = "CA";

$indexes = searchPattern($text, $pattern);

if (!empty($indexes)) {
   echo "Pattern found at indexes: " . implode(", ", $indexes);
} else {
   echo "Pattern not found";
}
?>

Output

Pattern found at indexes: 2, 5, 8

Explanation of code

The code implements the Naive algorithm for pattern searching in PHP. The searchPattern function takes two parameters: $text (the input text) and $pattern (the pattern to search for).Within the function, the lengths of the text and pattern are determined using the strlen function. An empty array called $foundIndexes is created to store the indexes where the pattern is found in the text.

The function then iterates through the text using a for loop, comparing each character with the corresponding character in the pattern. If a match is found, it continues comparing subsequent characters until either the entire pattern is matched or a mismatch occurs. If a complete match is found, the starting index is added to the $foundIndexes array.

In the example usage, the function is called with a sample text "ABCABCABCABC" and a pattern "CA". The resulting indexes where the pattern "CA" is found in the text are printed as output. Overall, the code demonstrates a basic implementation of the Naive algorithm in PHP, searching for a pattern within a given text and returning the indexes where the pattern occurs.

Conclusion

The provided PHP program implements the Naive algorithm for pattern searching. It searches for a given pattern within a text by comparing characters one by one. The algorithm iterates through the text and checks for a match at each position. If a match is found, it adds the starting index to an array. The program returns all the found indexes or indicates if the pattern is not found. While the Naive algorithm has a time complexity of O(m * n), where m is the pattern length and n is the text length, it serves as a basic and straightforward approach for small-scale pattern searching tasks in PHP.

The above is the detailed content of PHP Program for Naive Algorithm for Pattern Searching. For more information, please follow other related articles on the PHP Chinese website!