Current Location: Home> Latest Articles> Detailed Guide to PHP Naive String Matching Algorithm with Code Implementation

Detailed Guide to PHP Naive String Matching Algorithm with Code Implementation

M66 2025-06-15

1. Introduction to the Naive Algorithm

The naive algorithm is a basic and commonly used string matching method mainly applied in pattern searching. Its core idea is to start from the beginning of the text string and compare characters one by one with those in the pattern string. If the characters match, it continues to compare subsequent characters until a complete matching substring is found or the entire text has been traversed.

2. Implementation of the Naive Algorithm

2.1 Code Implementation

Below is the PHP implementation of the naive string matching algorithm:


function naive_search($text, $pattern) {
    $n = strlen($text);
    $m = strlen($pattern);
    for ($i = 0; $i <= $n - $m; $i++) {
        $j = 0;
        while ($j < $m && $text[$i + $j] == $pattern[$j]) {
            $j++;
        }
        if ($j == $m) {
            return $i;
        }
    }
    return -1;
}

This function accepts two string parameters: $text as the text to search within and $pattern as the substring to find. It returns the first position where the pattern occurs in the text, or -1 if no match is found. The algorithm uses nested loops to compare characters one by one, implementing a simple and clear matching logic.

2.2 Code Explanation

The function first calculates the lengths of the text and pattern strings, assigning them to variables $n and $m respectively. The outer loop iterates from the first character up to $n - $m to ensure comparisons do not exceed the text length.

The inner loop compares characters from both strings. When characters match, $j increments. If $j reaches $m, it means a full match is found and the function returns the starting index.

If no match is found after complete traversal, the function returns -1.

3. Applications of the Naive Algorithm

3.1 String Matching

The naive algorithm is primarily used for basic string matching problems, such as checking whether a substring exists within a text. Example:


$text = "Hello, world!";
$pattern = "world";
$result = naive_search($text, $pattern);
echo $result;  // Outputs 7

In this example, the function successfully finds the substring "world" in the text and returns its starting position 7.

3.2 Pattern Matching

Besides simple string matching, the naive algorithm can be applied to pattern searching, such as regex matching and HTML tag extraction. The following example demonstrates how to find all links in an HTML snippet:


$html = "<html><body><a href='http://example.com'>Example</a></body></html>";
$pattern = "<a href='(.*?)'>(.*?)</a>";
preg_match_all("/$pattern/s", $html, $matches);
print_r($matches);  // Outputs matched results

This example uses a regular expression combined with PHP's built-in preg_match_all function to extract all hyperlink tags from the HTML string, illustrating practical pattern search use cases.

4. Performance Analysis of the Naive Algorithm

The time complexity of the naive algorithm is O(nm), where n is the length of the text and m is the length of the pattern. Although its efficiency is relatively low, the simplicity and clarity make it acceptable for shorter patterns. For longer patterns, more efficient algorithms should be considered.

5. Conclusion

The naive algorithm is a straightforward and effective method for string matching, suitable for beginners to understand the basic concept of pattern searching. This article provides detailed PHP examples, explanations, and applications to help readers gain practical knowledge of string matching. Despite its performance limitations, the naive algorithm remains valuable for certain scenarios due to its ease of implementation and understanding.

Related