PHP implements a naive algorithm for pattern search (string matching algorithm)

Given text txt [0..n-1] and pattern pat [0..m-1], write a function to search (char pat [ ], char txt []) , print all occurrences of pat [] [] in txt. You can assumen> m.

Example:

输入:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
输出: Pattern found at index 10

输入:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
输出: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

Pattern search is an important problem in computer science. When we search for a string in Notepad, a word file, a browser, or a database, a pattern search algorithm is used to display the search results.

Naive Pattern Search:
Slide the pattern one by one through the text and check if it matches. If a match is found, slide 1 again to check for subsequent matches.

PHP code:

<?php 
// 朴素模式搜索算法
  
function search($pat, $txt) 
{ 
    $M = strlen($pat); 
    $N = strlen($txt); 
  
    for ($i = 0; $i <= $N - $M; $i++) 
    { 
  
        // 对于当前索引i，请检查模式匹配
        for ($j = 0; $j < $M; $j++) 
            if ($txt[$i + $j] != $pat[$j]) 
                break; 
  
        // if pat[0...M-1] =  
        // txt[i, i+1, ...i+M-1] 
        if ($j == $M)  
            echo "Pattern found at index ", $i."\n"; 
    } 
} 
  
    $txt = "AABAACAADAABAAABAA"; 
    $pat = "AABA"; 
    search($pat, $txt);

Output:

Pattern found at index 0 
Pattern found at index 9 
Pattern found at index 13

What is the best case scenario?

The best case occurs when the first character of the pattern does not exist in the text at all.

filter_none
brightness_4
txt[] = "AABCCAADDEE"; 
pat[] = "FAA";

The number of comparisons in the best case is O(n).

What is the worst case scenario?

1) When all characters of text and pattern are the same.

filter_none
brightness_4
txt[] = "AAAAAAAAAAAAAAAAAA"; 
pat[] = "AAAAA";

2) The worst case also occurs when the last character is different.

filter_none
brightness_4
txt[] = "AAAAAAAAAAAAAAAAAB"; 
pat[] = "AAAAB";

The worst case number of comparisons is O(m *(n-m 1)). Although strings with repeated characters are unlikely to appear in English text, they are likely to appear in other applications (for example, in binary text).

Related recommendations: "PHP Tutorial"

The above is the detailed content of PHP implements a naive algorithm for pattern search (string matching algorithm). For more information, please follow other related articles on the PHP Chinese website!