Problema
Per ogni pattern richiesto, determina se appare come sottostringa contigua in qualsiasi punto del testo condiviso. I pattern possono sovrapporsi e possono ripetersi. Restituisci i risultati nell'ordine originale delle query. I limiti richiedono un approccio che possa gestire molti pattern in modo efficiente.
Implementa find_many_patterns(text, patterns).
Input
text: Il testo su cui vengono effettuate tutte le ricerche.
patterns: I pattern, nell'ordine delle query.
Output
Restituisci YES per ogni pattern presente e NO per ciascuno assente.
Vincoli
1…100.000 caratteri nel testo. 1…100.000 pattern non vuoti, con lunghezza totale al massimo 500.000. Tutti i caratteri sono lettere minuscole da a a z.
Esempi
Input:
text = "bananas"
patterns = ["ana", "apple", "nas"]
Output atteso:
expected = ["YES", "NO", "YES"]Input:
std::string text = "bananas";
std::vector<std::string> patterns = {"ana", "apple", "nas"};
Output atteso:
std::vector<std::string> expected = {"YES", "NO", "YES"};Input:
string text = "bananas";
string[] patterns = new string[] {"ana", "apple", "nas"};
Output atteso:
string[] expected = new string[] {"YES", "NO", "YES"};Spiegazione
Ana compare a partire dalla posizione 2 e nas dalla posizione 5 (le posizioni qui partono da 1). Apple non compare mai.
Input:
text = "aaaa"
patterns = ["aa", "aaaaa", "aa"]
Output atteso:
expected = ["YES", "NO", "YES"]Input:
std::string text = "aaaa";
std::vector<std::string> patterns = {"aa", "aaaaa", "aa"};
Output atteso:
std::vector<std::string> expected = {"YES", "NO", "YES"};Input:
string text = "aaaa";
string[] patterns = new string[] {"aa", "aaaaa", "aa"};
Output atteso:
string[] expected = new string[] {"YES", "NO", "YES"};Spiegazione
Aa compare anche in caso di corrispondenze sovrapposte. Cinque caratteri a non possono entrare in un testo di quattro caratteri. La query ripetuta aa riceve la stessa risposta.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Più pattern possono condividere lavoro, quindi evita di cercare il testo separatamente per ogni query.
Suggerimento 2
Costruisci una sola struttura che memorizza tutti i pattern e scorri il testo una volta sola, avanzando nelle corrispondenze man mano che arrivano i caratteri.
Suggerimento 3
Fai attenzione a riportare i pattern ripetuti nell'ordine delle query e lascia che le sovrapposizioni contino in modo indipendente.
Complessità attesa
tempo O(text length + total pattern length), spazio aggiuntivo O(total pattern length)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.