Recherche de sous-chaînes
Étant donné un long texte t et une chaîne de caractères s, vous devez identifier toutes les occurrences de s dans le texte t. Votre tâche consiste à déterminer les positions de départ dans t où se trouve s.
Entrée
La première ligne de l’entrée contient le texte t (1 ≤ |t| ≤ ).
La deuxième ligne de l’entrée contient la chaîne s (1 ≤ |s| ≤ |t|).
Sortie
Pour chaque occurrence de s dans t, affichez la position de départ correspondante dans t. Les positions doivent apparaître dans l’ordre croissant (du début du texte vers la fin), séparées par un espace. L’indexation commence à 0.
Exemples
Entrée | Sortie |
|---|---|
habababohabo | 2 4 |
barfoobarfoobarfoobarfoobarfoo | 3 9 15 21 |
Explication
habababohabo → ha
bababohabo, habababohabobarfoobarfoobarfoobarfoobarfoo → bar
foobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB