Substring-Suche
Gegeben ist ein langer Text
t und eine Zeichenkette s. Die Aufgabe besteht darin, alle Vorkommen von s in dem Text t zu finden. Konkret sollen alle Startpositionen in t ermittelt werden, an denen s übereinstimmt.Eingabe
Die erste Zeile der Eingabe enthält den Text
t (1 ≤ |t| ≤ ).Die zweite Zeile enthält die Zeichenkette
s (1 ≤ |s| ≤ |t|).Ausgabe
Für jedes Vorkommen von
s in t soll die jeweilige Startposition in t ausgegeben werden. Diese Positionen müssen in aufsteigender Reihenfolge (vom Anfang bis zum Ende des Textes) durch ein Leerzeichen getrennt ausgegeben werden. Die Indexierung beginnt bei 0.Beispiele
Eingabe | Ausgabe |
habababohabo
ba | 2 4 |
barfoobarfoobarfoobarfoobarfoo
foobarfoo | 3 9 15 21 |
Erläuterung
- habababohabo → ha
bababohabo, habababohabo
- barfoobarfoobarfoobarfoobarfoo → bar
foobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB