Problem D
Dekompression
I denna uppgift ska du återskapa en text som har komprimerats med en algoritm som hittar ofta förekommande delsträngar och genererar en lista med vilka positioner de hittades på.
Som exempel så skulle “sju: 0 7; sjö: 4 13; ka: 10; män: 16” återskapas till “sju sjösjuka sjömän”.
Indata
En text, med som mest 100 000 000 tecken, formaterad som en serie av textdelar följda av ett kolon och en lista av positioner separerade av mellanslag. Texten består av en eller flera sådana serier, separerade av semikolon (“;”). Du kan anta att inget överlapp förekommer, dvs att olika tecken inte ska finnas på samma position i utdata. Du kan anta att texten som ska återskapas inte i sig innehåller några kolon eller semikolon.
Utdata
En icke radbruten text. De positioner där det inte explicit angetts att det ska vara något tecken ska innehålla ett mellanslag. Du kan anta att utdata inte är mer än 100 000 000 tecken.
| Sample Input 1 | Sample Output 1 |
|---|---|
sju: 0 7; sjö: 4 13; ka: 10; män: 16 |
sju sjösjuka sjömän |
| Sample Input 2 | Sample Output 2 |
|---|---|
h,: 18 24 51 57 84 90 96; h!: 30 63 102; She loves you,: 0 33 66; yea: 15 21 27 48 54 60 81 87 93 99; |
She loves you, yeah, yeah, yeah! She loves you, yeah, yeah, yeah! She loves you, yeah, yeah, yeah, yeah! |
