PHP implémente un algorithme naïf pour la recherche de modèles (algorithme de correspondance de chaînes)

Étant donné le texte txt [0..n-1] et le modèle pat [0..m-1], écrivez une fonction pour rechercher （char pat []，char txt []） et imprimer toutes les occurrences de pat [] [] en txt. Vous pouvez supposer n> m.

Exemple :

输入:  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

La recherche de modèles est un problème important en informatique. Lorsque nous recherchons une chaîne dans le Bloc-notes, un fichier Word, un navigateur ou une base de données, un algorithme de recherche de modèles est utilisé pour afficher les résultats de la recherche.

Recherche de motifs naïfs :
Faites glisser les motifs sur le texte un par un et vérifiez s'ils correspondent. Si une correspondance est trouvée, faites glisser à nouveau 1 pour vérifier les correspondances ultérieures.

Code PHP :

<?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);

Sortie :

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

Quel est le meilleur scénario ?

Le meilleur des cas se produit lorsque le premier caractère du motif n'existe pas du tout dans le texte.

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

Le nombre de comparaisons dans le meilleur des cas est de O（n）.

Quel est le pire des cas ?

1) Lorsque tous les caractères du texte et du motif sont identiques.

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

2) Le pire des cas se produit également lorsque le dernier caractère est différent.

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

Le pire nombre de comparaisons est O（m *（n-m + 1））. Bien qu'il soit peu probable que les chaînes contenant des caractères répétés apparaissent dans le texte anglais, elles apparaîtront probablement dans d'autres applications (par exemple, dans du texte binaire).

Recommandations associées : "Tutoriel PHP"

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!