ŽUPANIJSKO NATJECANJE 2013. / Srednja škola, II. podskupina (3. i 4. razred) - 3. zadatak

Hakeri prisluškuju komunikaciju Mirka i Slavka te pokušavaju razumjeti presretnute poruke.

Rječnik Mirka i Slavka sadrži M riječi te se svaka poruka koju jedan od njih pošalje drugome sastoji od niza riječi iz rječnika odvojenih razmacima.

Međutim, poruke koje hakeri presreću su zbog slabe kvalitete njihove opreme izmjenjene na sljedeći način:

1. U poruku je umetnuto najviše K šumova – proizvoljnih nizova slova. Svaki šum je uvijek umetnut između dvije riječi ili prije prve ili nakon zadnje riječi, dakle nikad unutar neke riječi.
2. Svi razmaci između riječi u poruci su izbrisani.

Na primjer ako Mirko pošalje poruku 'mirko slavko', kada je hakeri presretnu ona može biti 'mirkoxyzslavko', gdje je niz 'xyz' šum, a riječi 'mirko' i 'slavko' se nalaze u rječniku.

Hakerima je poznat njihov rječnik te su upravo zaprimili novu izmjenjenu poruku koju žele rastaviti na riječi iz riječnika i šumove.

Od svih mogućih načina na koji se to može napraviti zanima ih onaj gdje ima najviše moguće riječi iz rječnika.

Napišite program koji za zadani rječnik, zadani broj K, te zaprimljenu izmjenjenu poruku dobivenu na opisani način, određuje koliko najviše može biti riječi iz rječnika u rastavu, te određuje jedan (bilo koji) rastav u kojem je najviše moguće riječi iz rječnika.

Ulazni podaci

U prvom retku ulaza nalaze se cijeli brojevi M (1 ≤ M ≤ 1000) i K (0 ≤ K ≤ 10) – broj riječi u rječniku te najveći mogući broj šumova u pojedinoj primljenoj poruci.

U drugom retku ulaza nalazi se tekst primljene poruke – niz malih slova engleske abecede duljine N (1 ≤ N ≤ 10 000).

U svakom od sljedećih M redaka nalazi se jedna riječ u rječniku – niz od najmanje jednog, a najviše 20 malih slova engleske abecede.

Izlazni podaci

U prvom retku izlaza ispišite traženi maksimalan broj riječi iz rječnika u rastavljenoj poruci.

U drugom retku izlaza ispišite poruku u kojoj su riječi i šum odvojeni razmacima, u istom redoslijedu kao u poruci.

Svako pojavljivanje šuma ispišite kao niz uzastopnih znakova '#', duljine tog šuma.

Napomena: Rješenje, iako ne nužno jedinstveno, će uvijek postojati.

Primjeri test podataka

Ulaz

5 3
prisluskujuabcdnassumhakeri
mirko
nas
slavko
hakeri
prisluskuju

Izlaz

3
prisluskuju #### nas ### hakeri

Ulaz

6 0
dotheharlemshake
the
shake
do
mirko
harlem
slavko

Izlaz

4
do the harlem shake