Comment implémenter un algorithme de correspondance de chaînes avec PHP

Comment implémenter un algorithme de correspondance de chaînes en PHP

La correspondance de chaînes est l'un des problèmes importants en informatique. Elle est souvent utilisée dans les moteurs de recherche, les éditeurs de texte, l'exploration de données et d'autres domaines. Dans cet article, nous présenterons comment utiliser PHP pour implémenter deux algorithmes de correspondance de chaînes courants : la correspondance par force brute et l'algorithme KMP.

1. Algorithme de correspondance par force brute

L'algorithme de correspondance par force brute est l'algorithme de correspondance de chaînes le plus simple et le plus intuitif. Son idée est très simple, c'est-à-dire vérifier caractère par caractère dans la chaîne principale si elle correspond à la chaîne de modèle. S'il n'y a pas de correspondance, reculez d'un caractère et recommencez la correspondance ; s'il y a une correspondance, continuez à faire correspondre le caractère suivant jusqu'à ce qu'une correspondance soit trouvée ou que la chaîne principale entière soit parcourue.

Ce qui suit est un exemple de code pour un algorithme de correspondance par force brute implémenté en 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. Algorithme KMP

L'algorithme KMP est un algorithme de correspondance de chaîne efficace qui utilise les informations de la chaîne de modèle elle-même pour réduire les opérations de correspondance inutiles. Son idée principale est que pendant le processus de correspondance, lorsqu'une discordance est détectée, le nouveau point de départ de la correspondance est déterminé en fonction de la partie correspondante, au lieu de commencer à chaque fois par le caractère suivant de la chaîne principale.

Ce qui suit est un exemple de code de l'algorithme KMP implémenté en 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;

Grâce à l'exemple ci-dessus, nous pouvons voir que par rapport à l'algorithme de correspondance par force brute, l'algorithme KMP réduit le nombre de comparaisons de caractères inutiles et améliore l'efficacité de correspondance de chaînes.

Résumé :

Cet article présente comment utiliser PHP pour implémenter des algorithmes de correspondance de chaînes, y compris des algorithmes de correspondance par force brute et des algorithmes KMP. L'algorithme de correspondance par force brute est simple et intuitif, mais son efficacité est faible, tandis que l'algorithme KMP améliore l'efficacité de la correspondance en utilisant les informations de la chaîne de modèle elle-même. Dans les applications pratiques, selon différents scénarios et besoins, vous pouvez choisir un algorithme de correspondance de chaînes approprié pour améliorer les performances du programme.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!