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
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.
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.