Comment trouver des chaînes uniques en php

PHP est un langage de programmation Web très populaire, largement utilisé pour développer des sites Web dynamiques et des applications Web. Au cours du processus de développement, il est souvent nécessaire de traiter les chaînes, par exemple pour rechercher des chaînes uniques. Cet article explique comment utiliser PHP pour écrire un programme puissant permettant de trouver des chaînes uniques.

1. Qu'est-ce qu'une chaîne unique ? En informatique, une chaîne unique fait référence à une sous-chaîne sans caractères répétés dans une chaîne. Par exemple, dans la chaîne "hello world", les sous-chaînes non répétitives sont "hel", "helo", "hell", "hello", "wor", "world", etc.

2. Algorithme pour trouver des chaînes uniques

Pour trouver des chaînes uniques, nous devons utiliser un algorithme pour traiter les chaînes. Les algorithmes couramment utilisés incluent la « fenêtre coulissante » et la « table de hachage ».

Algorithme de fenêtre coulissante

1. L'algorithme de fenêtre coulissante est un algorithme de traitement de chaînes très efficace qui peut trouver des chaînes uniques dans une complexité temporelle O(n).

Les étapes de cet algorithme sont les suivantes :

1) Définissez deux pointeurs gauche et droit, pointant respectivement vers le premier caractère de la chaîne.

2) Utilisez une table de hachage pour enregistrer le nombre d'occurrences de chaque caractère.

3) Déplacez le pointeur droit vers la droite jusqu'à ce que vous rencontriez un caractère répétitif.

4) Déplacez le pointeur gauche vers la droite jusqu'à ce qu'il n'y ait plus de caractères répétés.

5) Répétez les étapes 3 et 4 jusqu'à ce que le pointeur droit atteigne la fin de la chaîne.

6) Calculez la longueur de chaque sous-chaîne non répétitive et trouvez la sous-chaîne non répétitive la plus longue.

Voici l'implémentation PHP de l'algorithme :

fonction findLongestSubstring($str){

$n = strlen($str);
$set = array();
$ans = $i = $j = 0;
while ($i < $n && $j < $n) {
    if (!isset($set[$str[$j]])) {
        $set[$str[$j++]] = true;
        $ans = max($ans, $j - $i);
    } else {
        unset($set[$str[$i++]]);
    }
}
return $ans;

}

Algorithme de table de hachage

2. L'algorithme de table de hachage est une structure de données utilisée pour une recherche rapide, qui permet de trouver rapidement si un élément existe dans une table de hachage. L'idée d'implémentation de cet algorithme est la suivante :

1) Utiliser une table de hachage pour stocker la position où les caractères apparaissent.

2) Parcourez la chaîne, si le caractère n'est pas dans la table de hachage, ajoutez-le à la table de hachage, sinon mettez à jour les informations de position du caractère.

3) Enregistrez les positions de début et de fin des sous-chaînes non répétitives.

4) Mettez à jour la longueur de la sous-chaîne la plus longue.

5) Renvoie la longueur de la sous-chaîne la plus longue.

Ce qui suit est l'implémentation PHP de cet algorithme :

fonction findLongestSubstring($str){

$n = strlen($str);
$map = array();
for ($i = $j = $ans = 0; $j < $n; $j++) {
    if (isset($map[$str[$j]])) {
        $i = max($map[$str[$j]], $i);
    }
    $ans = max($ans, $j - $i + 1);
    $map[$str[$j]] = $j + 1;
}
return $ans;

}

3. Programme de test

Afin de vérifier l'exactitude de l'algorithme ci-dessus, nous avons écrit un programme de test. Ce programme peut générer aléatoirement une chaîne et utiliser les deux algorithmes ci-dessus pour trouver la sous-chaîne non répétitive la plus longue. Nous pouvons exécuter le programme en boucle pour vérifier l'exactitude et le temps d'exécution de l'algorithme.

Ce qui suit est le code PHP du programme de test :

function randomString($length = 10) {

$str = '';
$chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
for ($i = 0; $i < $length; $i++) {
    $str .= $chars[rand(0, strlen($chars) - 1)];
}
return $str;

}

$N = 5;

for ($i = 0; $i < $N; $i++) {

$str = randomString(100000);
$start = microtime();
$ans1 = findLongestSubstring($str);
$end = microtime();
$time1 = ($end - $start) * 1000;

$start = microtime();
$ans2 = findLongestSubstring($str);
$end = microtime();
$time2 = ($end - $start) * 1000;

printf("Test case %d: %s\n", $i + 1, $str);
printf("滑动窗口算法: %d (%.3fms)\n", $ans1, $time1);
printf("哈希表算法: %d (%.3fms)\n", $ans2, $time2);

}

IV. Résumé

Cet article explique comment utiliser PHP pour écrire un programme permettant de trouver des sous-chaînes uniques et présente deux algorithmes couramment utilisés : l'algorithme de fenêtre glissante et l'algorithme de table de hachage. L'algorithme de fenêtre glissante est un algorithme efficace avec une complexité temporelle de O(n) et convient au traitement de données à grande échelle ; l'algorithme de table de hachage est plus contrôlable en termes d'utilisation de l'espace, mais sa complexité temporelle est élevée. Les procédures de test du programme peuvent nous aider à vérifier le temps d'exécution et l'exactitude de l'algorithme, afin de sélectionner l'algorithme le plus adapté au scénario actuel.

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!