Ricerca di sottostringa
Dato un testo lungo
t e una stringa s, si richiede di trovare tutte le occorrenze di s nel testo t. In particolare, bisogna individuare le posizioni di inizio in t in cui s corrisponde.Input
La prima riga dell’input contiene il testo
t (1 ≤ |t| ≤ ).La seconda riga dell’input contiene la stringa
s (1 ≤ |s| ≤ |t|).Output
Per ogni occorrenza di
s in t, bisogna stampare la posizione di inizio in t in cui si verifica. Le posizioni vanno elencate in ordine crescente (dall’inizio del testo fino alla fine) e separate da uno spazio. L’indicizzazione parte da 0.Esempi
Ingresso | Uscita |
habababohabo
ba | 2 4 |
barfoobarfoobarfoobarfoobarfoo
foobarfoo | 3 9 15 21 |
Spiegazione
- habababohabo → ha
bababohabo, habababohabo
- barfoobarfoobarfoobarfoobarfoo → bar
foobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB