Todos los desafíos
Difícil 1 resuelto 100.0% de aceptación

Find Many Patterns in Text

For each requested pattern, decide whether it appears as a contiguous substring anywhere in the shared text.

Lo que aprenderás

  • Comprobar muchos patrones en un texto rápidamente
  • Preprocesar el texto o los patrones para búsquedas rápidas
  • Comparar la búsqueda ingenua con la indexada

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

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

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

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 848 ms - 4/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 1 solución completa abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.