Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Find Many Patterns in Text

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

Das lernst du

  • Viele Muster schnell gegen einen Text prüfen
  • Text oder Muster für schnelle Abfragen vorverarbeiten
  • Naive Suche mit indizierter Suche vergleichen

Problem

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.

Einschränkungen

1…100,000 text characters. 1…100,000 nonempty patterns, with total length at most 500,000. All characters are lowercase a–z.

Beispiele

Beispiel 1
Eingabe:
text = "bananas"
patterns = ["ana", "apple", "nas"]

Erwartete Ausgabe:
expected = ["YES", "NO", "YES"]
Eingabe:
std::string text = "bananas";
std::vector<std::string> patterns = {"ana", "apple", "nas"};

Erwartete Ausgabe:
std::vector<std::string> expected = {"YES", "NO", "YES"};
Eingabe:
string text = "bananas";
string[] patterns = new string[] {"ana", "apple", "nas"};

Erwartete Ausgabe:
string[] expected = new string[] {"YES", "NO", "YES"};

Erläuterung

Ana appears starting at position 2 and nas at position 5 (positions start at 1 here). Apple never appears.

Beispiel 2
Eingabe:
text = "aaaa"
patterns = ["aa", "aaaaa", "aa"]

Erwartete Ausgabe:
expected = ["YES", "NO", "YES"]
Eingabe:
std::string text = "aaaa";
std::vector<std::string> patterns = {"aa", "aaaaa", "aa"};

Erwartete Ausgabe:
std::vector<std::string> expected = {"YES", "NO", "YES"};
Eingabe:
string text = "aaaa";
string[] patterns = new string[] {"aa", "aaaaa", "aa"};

Erwartete Ausgabe:
string[] expected = new string[] {"YES", "NO", "YES"};

Erläuterung

Aa occurs despite overlapping matches. Five a characters cannot fit in a four-character text. The repeated aa query receives the same answer.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Viele Muster können sich Arbeit teilen, also suche nicht für jede Anfrage separat im Text.

Hinweis 2

Baue eine Struktur, die alle Muster speichert, und scanne den Text nur einmal, während du Treffer bei jedem Zeichen weiterführst.

Hinweis 3

Achte darauf, wiederholte Muster in der Reihenfolge der Anfragen auszugeben, und lass überlappende Treffer unabhängig zählen.

Erwartete Komplexität

Zeit O(text length + total pattern length), zusätzlicher Speicher O(total pattern length)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 848 ms - 4/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.