Problema
For each requested pattern, decide whether it appears as a contiguous substring anywhere in the shared text. Patterns may overlap and may repeat. Return results in the original query order. The limits require an approach that can handle many patterns efficiently.
Implement find_many_patterns(text, patterns).
Input
text: The text searched by every query.
patterns: The patterns, in query order.
Output
Return YES for each occurring pattern and NO for each absent one.
Restricciones
1…100,000 text characters. 1…100,000 nonempty patterns, with total length at most 500,000. All characters are lowercase a–z.
Ejemplos
Entrada:
text = "bananas"
patterns = ["ana", "apple", "nas"]
Salida esperada:
expected = ["YES", "NO", "YES"]Entrada:
std::string text = "bananas";
std::vector<std::string> patterns = {"ana", "apple", "nas"};
Salida esperada:
std::vector<std::string> expected = {"YES", "NO", "YES"};Entrada:
string text = "bananas";
string[] patterns = new string[] {"ana", "apple", "nas"};
Salida esperada:
string[] expected = new string[] {"YES", "NO", "YES"};Explicación
Ana appears starting at position 2 and nas at position 5 (positions start at 1 here). Apple never appears.
Entrada:
text = "aaaa"
patterns = ["aa", "aaaaa", "aa"]
Salida esperada:
expected = ["YES", "NO", "YES"]Entrada:
std::string text = "aaaa";
std::vector<std::string> patterns = {"aa", "aaaaa", "aa"};
Salida esperada:
std::vector<std::string> expected = {"YES", "NO", "YES"};Entrada:
string text = "aaaa";
string[] patterns = new string[] {"aa", "aaaaa", "aa"};
Salida esperada:
string[] expected = new string[] {"YES", "NO", "YES"};Explicación
Aa occurs despite overlapping matches. Five a characters cannot fit in a four-character text. The repeated aa query receives the same answer.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Muchos patrones pueden compartir trabajo, así que evita buscar el texto por separado para cada consulta.
Pista 2
Construye una sola estructura que guarde todos los patrones y recorre el texto una vez, avanzando coincidencias a medida que llegan los caracteres.
Pista 3
Ten cuidado de reportar los patrones repetidos en el orden de la consulta y deja que las coincidencias superpuestas cuenten por separado.
Complejidad esperada
tiempo O(text length + total pattern length), espacio extra O(total pattern length)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.