Naive algorithm for PHP program for pattern search

What is PHP?

PHP (Hypertext Preprocessor) is a web development language widely used as a server-side scripting language. It allows developers to embed code in HTML files to create dynamic web pages and interact with databases. PHP is known for its simplicity, versatility, and extensive integration capabilities with popular databases. It offers a wide range of extensions and has a large developer community ensuring abundant resources and support

What is the 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 accepts two parameters: the text to be searched and the pattern to be searched. The algorithm works by looping through the text, comparing each character to the corresponding character in the pattern. If a non-matching character is found, it moves to the next character in the text and starts the comparison again. If a matching character is found, it will continue comparing subsequent characters until the entire pattern matches or a mismatch occurs

PHP program for pattern search using Naive algorithm

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

Code explanation

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 match is found, it continues comparing subsequent characters until either the entire pattern is matched or a mismatch occurs. 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 output is the index in the text at which pattern "CA" was found. Overall, this code shows a basic implementation of the Naive algorithm in PHP for searching for a pattern in a given text and returning the index of occurrence of the pattern

in conclusion

The provided PHP program implements the Naive algorithm for pattern search. It searches the text for a given pattern by comparing it character by character. The algorithm goes 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 found indices, or indicates that the pattern was not found. Although the time complexity of the Naive algorithm is O(m * n), where m is the pattern length and n is the text length, it serves as a basic and straightforward method for small-scale pattern search tasks in PHP.

The above is the detailed content of Naive algorithm for PHP program for pattern search. For more information, please follow other related articles on the PHP Chinese website!