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. Požrešni algoritmi
  3. Vzorec

Vzorec

Completion requirements
Due: Sunday, 8 December 2024, 11:59 PM

Podan je vzorec $S$, ki poleg črk vsebuje še posebna znaka ? in *. Poleg tega je podan še niz $T$. Napišite program, ki ugotovi, ali se niz $T$ kje ujema s podanim vzorcem $S$. Posebni znak * lahko v ujemanju zavzame poljubno zaporedje nič ali več znakov. Posebni znak ? pa zavzame natanko en poljuben znak.

Nizi bodo sestavljeni iz malih črk angleške abecede, znaka _ in posebnih znakov ? in *.

Omejitve podatkov:

  • $N\leq 50$
  • $1 \leq |S|, |T| \leq 1000$

Vhodni in izhodni podatki:

Vhodni podatki imajo sledečo strukturo. Prva vrstica vsebuje število $N$, ki določa število parov $S$, $T$. V naslednjih $N$ vrsticah so zapisani pari $S$, $T$, ki so ločeni s presledkom.

Za vsak par $S$, $T$ izpišite v svoji vrstici začetni in končni indeks prvega (z najmanjšim indeksom začetka) nepraznega podniza v $T$, ki se ujema z vzorcem $S$. Če je takih podnizov več, izpišite konec najkrajšega takšnega podniza. Če ujemanja ni, izpišite -1.

Primer vhoda:

5
is?ani_vz**or*?c?ne**?vs*je?znaka??? oksimoron_je_da_iskani_vzorec_ne_vsebuje_znaka_abc
???*??* asdf
* dfweqr_adsfadsf_sfdgsgd_fsgsdgs_fgscgdg
lal*enelc*uc* luysznnmqlaldiinlsenelcqudmwvqholjaijlsucygcnn_gol
*p?*?*_zvez*i??* tudi_to_je_del_resitve__poisci_zvezdico_to_pa_ne

Pravilen izhod:

16 48
-1
0 0
9 40
0 38
You are currently using guest access (Log in)
Get the mobile app
Powered by Moodle
Obvestilo o avtorskih pravicah