Tous les défis
Difficile 1 résolu 100.0 % de réussite

Trouver Plusieurs Motifs dans un Texte

Pour chaque motif demandé, déterminer s'il apparaît comme sous-chaîne contiguë n'importe où dans le texte commun.

Ce que vous allez apprendre

  • Vérifier rapidement de nombreux motifs dans un texte
  • Prétraiter le texte ou les motifs pour des recherches rapides
  • Comparer recherche naïve et recherche indexée

Problème

Pour chaque motif demandé, déterminer s'il apparaît comme sous-chaîne contiguë n'importe où dans le texte commun. Les motifs peuvent se chevaucher et se répéter. Retournez les résultats dans l'ordre original des requêtes. Les limites imposent une approche capable de traiter efficacement de nombreux motifs.

Implémentez find_many_patterns(text, patterns).

Entrée

text : Le texte dans lequel chaque requête effectue sa recherche.

patterns : Les motifs, dans l'ordre des requêtes.

Sortie

Retournez YES pour chaque motif présent et NO pour chaque motif absent.

Contraintes

1…100 000 caractères pour le texte. 1…100 000 motifs non vides, avec une longueur totale d'au plus 500 000. Tous les caractères sont des lettres minuscules de a à z.

Exemples

Exemple 1
Entrée :
text = "bananas"
patterns = ["ana", "apple", "nas"]

Sortie attendue :
expected = ["YES", "NO", "YES"]
Entrée :
std::string text = "bananas";
std::vector<std::string> patterns = {"ana", "apple", "nas"};

Sortie attendue :
std::vector<std::string> expected = {"YES", "NO", "YES"};
Entrée :
string text = "bananas";
string[] patterns = new string[] {"ana", "apple", "nas"};

Sortie attendue :
string[] expected = new string[] {"YES", "NO", "YES"};

Explication

Ana apparaît à partir de la position 2 et nas à la position 5 (les positions commencent à 1 ici). Apple n'apparaît jamais.

Exemple 2
Entrée :
text = "aaaa"
patterns = ["aa", "aaaaa", "aa"]

Sortie attendue :
expected = ["YES", "NO", "YES"]
Entrée :
std::string text = "aaaa";
std::vector<std::string> patterns = {"aa", "aaaaa", "aa"};

Sortie attendue :
std::vector<std::string> expected = {"YES", "NO", "YES"};
Entrée :
string text = "aaaa";
string[] patterns = new string[] {"aa", "aaaaa", "aa"};

Sortie attendue :
string[] expected = new string[] {"YES", "NO", "YES"};

Explication

Aa apparaît malgré les occurrences qui se chevauchent. Cinq caractères a ne peuvent pas tenir dans un texte de quatre caractères. La requête répétée aa reçoit la même réponse.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Plusieurs motifs peuvent partager du travail, donc évite de rechercher le texte séparément pour chaque requête.

Indice 2

Construis une seule structure qui stocke tous les motifs et parcoure le texte une fois, en faisant avancer les correspondances au fil des caractères.

Indice 3

Fais attention à signaler les motifs répétés dans l’ordre des requêtes, et laisse les correspondances qui se chevauchent compter indépendamment.

Complexité attendue

temps O(text length + total pattern length), espace supplémentaire O(total pattern length)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 848 ms - 4/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.