Français
Français
Les algorithmes naïfs sont une méthode de correspondance de chaîne de base et intuitive, souvent utilisée pour rechercher des chaînes de motifs spécifiques dans le texte. L'algorithme compare les caractères du texte et de la chaîne de modèle un par un du premier caractère du texte pour déterminer si la position correspondante ou la fin du texte est trouvée.
Ce qui suit est l'exemple de code de l'algorithme de correspondance de chaîne naïf implémenté à l'aide de PHP:
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;
}
La fonction accepte deux paramètres de chaîne, $ text est le texte à rechercher et $ motif est la chaîne de modèle qui doit être appariée. L'algorithme compare le texte et le caractère de modèle par caractère à travers la boucle à double couche. Lorsque le match réussit, il renvoie la première position d'occurrence, et si elle ne correspond pas, elle renvoie -1.
Dans la fonction, les variables $ n et $ m représentent respectivement les longueurs du texte et du modèle. La boucle externe contrôle la plage de balayage du texte pour garantir que la partie restante est suffisante pour correspondre à la longueur du motif. La boucle intérieure compare le texte avec le caractère de modèle par caractère jusqu'à ce qu'il soit constaté que le match est un décalage ou le match est terminé. Renvoie l'index de départ lorsque le match réussit, sinon -1 sera renvoyé après la fin de la boucle.
Les algorithmes naïfs sont souvent utilisés pour des recherches de chaînes simples, telles que la détection si une sous-chaîne existe dans le texte. L'exemple de code est le suivant:
$text = "Hello, world!";
$pattern = "world";
$result = naive_search($text, $pattern);
echo $result; // Sortir 7
Dans cet exemple, $ text est la chaîne cible et le modèle $ est la sous-chaîne à trouver. La valeur de retour de fonction est l'indice de la position où la sous-chaîne apparaît d'abord.
En plus des recherches de chaînes simples, les algorithmes naïfs peuvent également aider à des tâches de correspondance de motifs, telles que les recherches basées sur l'expression. L'exemple suivant montre comment trouver tous les liens dans le code HTML:
$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); // Sortir匹配结果
Dans cet exemple, le modèle d'expression régulière est utilisé pour trouver tous les liens dans HTML et les résultats du tableau de correspondance de retour.
La complexité temporelle de l'algorithme naïf est O (nm), où n est la longueur du texte et m est la longueur du motif. Bien que les performances ne soient pas aussi bonnes que celles des algorithmes avancés, sa structure est simple et facile à comprendre et à mettre en œuvre. Pour les recherches de chaînes en mode court, les performances sont acceptables; Cependant, à mesure que la longueur de la chaîne de mode augmente, l'efficacité diminue considérablement, de sorte qu'un algorithme de recherche de chaînes plus efficace est généralement sélectionné dans des applications pratiques.
En tant qu'algorithme de correspondance de chaîne le plus basique, l'algorithme naïf présente les avantages d'une implémentation simple et intuitive et convient aux tâches de recherche de motifs de base. Il compare le texte et les modèles de caractère par caractère pour obtenir un processus clair. Malgré les limites en termes d'efficacité, il a toujours une valeur pratique pour de nombreuses applications pratiques, en particulier les scénarios qui traitent des chaînes de mode courts.
