English
English
The naive algorithm is a basic and intuitive string matching method commonly used to search for a specific pattern in a text. It works by comparing the characters of the text and pattern one by one, starting from the first character of the text, until a full match is found or the end of the text is reached.
Below is a PHP example implementing 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;
}
The function takes two string parameters: $text (the text to search) and $pattern (the pattern to find). It uses nested loops to compare characters between the text and pattern, returning the first occurrence index if matched, or -1 if not found.
Variables $n and $m represent the lengths of the text and pattern respectively. The outer loop scans the text ensuring enough characters remain to match the pattern length. The inner loop compares characters sequentially until mismatch or full match occurs. Upon a complete match, the function returns the starting index; otherwise, -1 is returned after completion.
The naive algorithm is commonly used for simple substring searches, such as checking if a substring exists within a string. Example:
$text = "Hello, world!";
$pattern = "world";
$result = naive_search($text, $pattern);
echo $result; // Outputs 7
Here, $text is the target string and $pattern is the substring to find. The function returns the index of the substring's first occurrence.
Besides basic substring searches, the naive algorithm can assist in pattern matching tasks such as regex-based searches. The example below demonstrates how to find all links in HTML code:
$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 regex pattern to find all anchor tags in the HTML string, storing matches in an array.
The time complexity of the naive algorithm is O(nm), where n is the text length and m is the pattern length. Although less efficient than advanced algorithms, it is simple and easy to understand. It performs adequately with short patterns but efficiency decreases sharply with longer patterns, prompting the use of more efficient algorithms in practical applications.
The naive algorithm is one of the most basic string matching methods, valued for its simplicity and straightforward implementation, suitable for basic pattern searching tasks. It compares text and pattern characters sequentially, making the logic easy to follow. Despite its limitations in performance, it remains useful for many real-world scenarios, especially those involving short pattern strings.
