Français
Français
L'algorithme naïf est une méthode de correspondance de chaîne de base et couramment utilisée, principalement utilisée pour la recherche de motifs. L'idée principale est de commencer à partir de la position de départ de la chaîne de texte et de comparer le caractère par caractère si les caractères dans la chaîne de texte et la chaîne de modèle sont les mêmes. S'il correspond, continuez à comparer les caractères ultérieurs jusqu'à ce que la sous-chaîne correspondante ou la traversée texte soit trouvée.
Ce qui suit est l'algorithme de correspondance de chaîne naïf implémenté par le langage 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;
}
Cette fonction reçoit deux paramètres de chaîne, $ le texte représente la chaîne de texte à rechercher et $ motif est la chaîne de modèle à rechercher. La fonction renvoie la position où la chaîne de modèle apparaît d'abord dans la chaîne de texte, et si elle n'est pas trouvée, il renvoie -1. L'algorithme réalise la logique de correspondance simple et claire via une comparaison de caractères à double boucle.
La fonction calcule d'abord les longueurs de la chaîne de texte et de la chaîne de modèle, et attribue des valeurs aux variables $ n $ et $ m $ respectivement. La boucle extérieure commence à partir du premier caractère de la chaîne de texte et des boucles au plus $ nm $, garantissant que les comparaisons ultérieures ne dépasseront pas la longueur du texte.
La boucle intérieure est utilisée pour comparer le texte et les chaînes de motifs par caractère, et $ j $ est incrémenté lorsqu'il est apparié. Lorsque $ j $ est égal à $ m $, la correspondance complète est trouvée et la position de démarrage du match est retournée.
Si le match n'est pas trouvé à la fin de la traversée, la fonction renvoie -1.
Les algorithmes naïfs sont principalement utilisés dans les problèmes de correspondance de la chaîne de base, tels que la recherche de si le texte contient une sous-chaîne spécifiée. Les exemples sont les suivants:
$text = "Hello, world!";
$pattern = "world";
$result = naive_search($text, $pattern);
echo $result; // Sortir 7
Dans cet exemple, la fonction trouve avec succès la position de la sous-chaîne "monde" dans le texte, avec la valeur de retour de 7.
En plus de la correspondance de base de la chaîne, les algorithmes naïfs peuvent également être utilisés dans les recherches de motifs, telles que la correspondance d'expression régulière, les recherches de balises HTML et d'autres scénarios. L'exemple suivant montre comment trouver tous les liens dans une page 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匹配结果
Cet exemple utilise des expressions régulières et des fonctions intégrées PHP pour extraire les balises de liaison dans HTML, montrant l'application pratique de la recherche de motifs.
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 son efficacité soit relativement faible, en raison de sa mise en œuvre simple et intuitive, les performances sont acceptables pour les chaînes de mode court. Lorsque vous traitez des chaînes de motifs plus longues, des algorithmes de correspondance plus efficaces doivent être considérés comme améliorant les performances.
L'algorithme naïf est une méthode de correspondance de cordes simple et efficace, adaptée pour démarrer et comprendre le mécanisme de recherche de motif de base. Cet article explique les principes d'algorithme, la mise en œuvre du code et les scénarios d'application en détail via des exemples PHP, fournissant une référence pratique aux lecteurs pour maîtriser la correspondance des chaînes. Bien que l'algorithme ait des limitations de performances, sa facilité de compréhension et de mise en œuvre le rend toujours utile dans certains scénarios.
