Skip to main content
Učilnica FRI 24/25
  • Home
  • More
Close
Toggle search input
English ‎(en)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
You are currently using guest access
Log in
Učilnica FRI 24/25
Home
Expand all Collapse all
  1. aps1uni
  2. Dinamično programiranje
  3. Presledki

Presledki

Completion requirements
Due: Sunday, 12 November 2023, 11:59 PM

V besedilu (zaporedju besed) smo izgubili vse presledke. Poznamo pa slovar besed, s pomočjo katerega želimo rekonstruirati originalno besedilo s presledki.

Besedilo je podano kot niz $S$ sestavljen iz velikih črk angleške abecede. Slovar besed je podan kot seznam $K$ nizov $B_i$, ki po dolžini ne presegajo 20 črk. Rekonstrukcija bo zagotov obstajala, morda jih bo obstajalo celo več. Vsako rekonstrukcijo lahko definiramo s seznamom dolžin besed. V primeru več rekonstrukcij želimo izbrati tako, ki bo imela leksikografsko najmanjši seznam dolžin besed (na začetku želimo torej čim krajše besede).

Omejitve podatkov:

  • $1 \leq |S| \leq 100\,000$
  • $1 \leq K \leq 10\,000$
  • $1 \leq |B_i| \leq 20$

Vhodni in izhodni podatki:

V prvi vrstici je podan niz $S$ brez presledkov. V drugi vrstici je podana velikost slovarja $K$. Sledečih $K$ vrstic pa vsebuje besede iz slovarja $B_i$.

Izpišite rekonstrukcijo besedila s presledki.

Primer vhoda:

ABCAACAAAAAAA
5
AB
AAA
CA
ABC
AA

Pravilen izhod:

ABC AA CA AA AA AA
You are currently using guest access (Log in)
Get the mobile app
Powered by Moodle
Obvestilo o avtorskih pravicah