How to implement string matching algorithm with PHP

How to use PHP to implement string matching algorithm

String matching is one of the important issues in computer science. It is often used in search engines, text editors, data mining and other fields. In this article, we will introduce how to use PHP to implement two common string matching algorithms: brute force matching and KMP algorithm.

1. Violent matching algorithm

The violent matching algorithm is the simplest and most intuitive string matching algorithm. Its idea is very simple, that is, checking character by character in the main string whether it matches the pattern string. If there is no match, move one character back and start matching again; if there is a match, continue matching the next character until a match is found or the entire main string is traversed.

The following is a sample code for a brute force matching algorithm implemented in PHP:

function bruteForce($str, $pattern) {
    $n = strlen($str);
    $m = strlen($pattern);
    
    for ($i = 0; $i <= $n - $m; $i++) {
        $j = 0;
        while ($j < $m && $str[$i+$j] == $pattern[$j]) {
            $j++;
        }
        
        if ($j == $m) {
            return $i; // 匹配成功，返回匹配的起始位置
        }
    }
    
    return -1; // 匹配失败，返回-1
}

$str = "Hello, World!";
$pattern = "World";
$position = bruteForce($str, $pattern);
echo "The position of the pattern is: " . $position;

2. KMP algorithm

The KMP algorithm is an efficient string matching algorithm , which uses the information of the pattern string itself to reduce unnecessary matching operations. Its core idea is that during the matching process, when a mismatch is found, the new matching starting point is determined based on the matched part, instead of starting from the next character of the main string every time.

The following is a sample code of the KMP algorithm implemented in PHP:

function calculateNext($pattern) {
    $m = strlen($pattern);
    $next[0] = -1;
    $i = 0;
    $j = -1;
    
    while ($i < $m - 1) {
        if ($j == -1 || $pattern[$i] == $pattern[$j]) {
            $i++;
            $j++;
            $next[$i] = $j;
        } else {
            $j = $next[$j];
        }
    }
    
    return $next;
}

function kmp($str, $pattern) {
    $n = strlen($str);
    $m = strlen($pattern);
    $next = calculateNext($pattern);
    $i = 0;
    $j = 0;
    
    while ($i < $n && $j < $m) {
        if ($j == -1 || $str[$i] == $pattern[$j]) {
            $i++;
            $j++;
        } else {
            $j = $next[$j];
        }
    }
    
    if ($j == $m) {
        return $i - $j; // 匹配成功，返回匹配的起始位置
    }
    
    return -1; // 匹配失败，返回-1
}

$str = "Hello, World!";
$pattern = "World";
$position = kmp($str, $pattern);
echo "The position of the pattern is: " . $position;

Through the above example, we can see that the KMP algorithm reduces the number of unnecessary character comparisons compared to the brute force matching algorithm. Improved string matching efficiency.

Summary:

This article introduces how to use PHP to implement string matching algorithms, including brute force matching algorithms and KMP algorithms. The brute force matching algorithm is simple and intuitive, but has low efficiency; while the KMP algorithm improves the matching efficiency by utilizing the information of the pattern string itself. In practical applications, according to different scenarios and needs, you can choose a suitable string matching algorithm to improve program performance.

The above is the detailed content of How to implement string matching algorithm with PHP. For more information, please follow other related articles on the PHP Chinese website!