Comptez le nombre de sous-chaînes de longueur M qui apparaissent exactement K fois dans une chaîne

Dans cet article, nous allons nous plonger dans un problème unique et fascinant dans le domaine de l'informatique : "Compter les sous-chaînes de longueur M qui apparaissent exactement K fois dans une chaîne". Ce type de question est souvent posé lors des concours de programmation et des entretiens. Avant de commencer, définissons à quoi nous avons affaire -

• Substring− Une séquence contiguë trouvée dans une autre chaîne.

• M length− La longueur de la sous-chaîne qui nous intéresse.

• K fois − Le nombre exact de fois où la sous-chaîne doit apparaître dans la chaîne d'origine.

Description de l'algorithme

Pour résoudre ce problème, nous allons profiter de la puissance des cartes de hachage (également appelées cartes non ordonnées en C++). Les cartes de hachage nous permettent de stocker des données sous forme de paires clé-valeur et fournissent une complexité temporelle constante pour les opérations de recherche et d'insertion, ce qui en fait un excellent outil pour résoudre de tels problèmes.

L'algorithme de calcul de la sous-chaîne de longueur M qui apparaît exactement K fois dans une chaîne est le suivant -

• Initialisez une carte de hachage vide.

• Parcourez la chaîne, créant toutes les sous-chaînes possibles de longueur M.

• Pour chaque sous-chaîne, ajoutez-la à la carte de hachage. S'il existe déjà, augmentez son nombre.

• Une fois que toutes les sous-chaînes ont été calculées, parcourez la carte de hachage pour trouver toutes les sous-chaînes qui apparaissent exactement K fois.

Implémentation C++

Il s'agit d'une implémentation C++ de l'algorithme ci-dessus -

Exemple

#include<bits/stdc++.h>
using namespace std;

int countSubstrings(string s, int M, int K) {
   unordered_map<string, int> count_map;
   int n = s.length();
   
   for (int i = 0; i <= n - M; i++) {
      string substring = s.substr(i, M);
      count_map[substring]++;
   }
   
   int count = 0;
   for (auto it : count_map) {
      if (it.second == K)
         count++;
   }

    return count;
}

int main() {
   string s = "abcabcabc";
   int M = 3;
   int K = 3;
   
   int result = countSubstrings(s, M, K);
   cout << "The number of M-length substrings occurring exactly K times is: " << result << endl;
   
   return 0;
}

Sortie

The number of M-length substrings occurring exactly K times is: 1

Dans le code ci-dessus, la fonction countSubstrings prend la chaîne d'entrée s, la longueur de la sous-chaîne M et le nombre d'occurrences K comme paramètres. Il initialise une carte non ordonnée count_map pour garder une trace de toutes les sous-chaînes et de leurs occurrences. Il parcourt ensuite la chaîne pour créer toutes les sous-chaînes possibles de longueur M, et pour chaque sous-chaîne, il incrémente le nombre dans la carte. Une fois que toutes les sous-chaînes ont été calculées, il parcourt la carte pour compter toutes les sous-chaînes qui apparaissent exactement K fois.

La fonction principale est l'endroit où commence l'exécution du code. Il initialise la chaîne s et les valeurs de M et K. Appelez ensuite la fonction countSubstrings et imprimez le résultat.

Exemple de cas de test

Considérons la chaîne "abcabcabc" où M=3 et K=3.

Ici, les sous-chaînes de longueur M sont "abc", "bca", "cab", "abc", "bca", "cab", "abc". Évidemment, la sous-chaîne "abc" apparaît exactement 3 fois dans la chaîne, donc la sortie du programme sera 1.

Cette approche du problème, où nous utilisons une carte de hachage pour calculer des sous-chaînes, est un bon exemple du compromis espace-temps en informatique. Lorsque nous utilisons de l'espace supplémentaire pour stocker les sous-chaînes et leur nombre, nous pouvons réduire considérablement la complexité temporelle du problème en comptant les occurrences en temps constant.

Complexité temporelle et spatiale

La complexité temporelle de cet algorithme est O(n), où n est la longueur de la chaîne. En effet, nous parcourons la chaîne une seule fois pour créer toutes les sous-chaînes possibles de longueur M.

En raison des exigences de stockage de la carte de hachage, la complexité spatiale est également O(n), dans le pire des cas, chaque sous-chaîne est unique, ce qui entraîne n entrées différentes dans la carte.

Conclusion

Dans cet article, nous étudions un problème courant en informatique : compter le nombre de sous-chaînes de longueur M qui apparaissent exactement K fois dans une chaîne. Nous avons implémenté une solution efficace en C++ utilisant des cartes de hachage, ce qui nous a permis d'effectuer des opérations de recherche et d'insertion en temps constant. Ce problème est un exemple parfait de la façon dont les structures de données et les algorithmes peuvent être utilisés ensemble pour résoudre efficacement des problèmes complexes.

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!