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

Rezultati državne mature su stigli! Iako se Mirko približno sjeća lozinke koju je zadnji puta koristio prije nekoliko dana, od silnog uzbuđenja zaboravio je točan oblik i nikako se ne uspjeva prijaviti na sustav.

Odlučio je ispisati sve lozinke koje se podudaraju s pojedinostima tj. s uzorkom kojeg se Mirko mutno sjeća.

Mirkova lozinka je niz od jednog ili više malih slova engleske abecede. Uzorak je niz znakova koji se definira na sljedeći način:

• Svaki niz od jednog ili više malih slova engleske abecede je uzorak.
• Ako su u1 i u2 uzorci, onda je niz koji dobijemo njihovim spajanjem 'u1u2' također uzorak
• Ako su u1, u2, ..., uK dva ili više (ne nužno različitih) uzoraka onda je također i niz znakova '(u1|u2|...|uk)' uzorak. Drugim riječima, od niza od dva ili više uzoraka možemo napraviti novi uzorak tako da nizove napišemo jedan za drugim odvojene vertikalnom crtom '|', te sve skupa stavimo u zagrade.

Tako su, na primjer, 'abc', '(a|a|b)' i 'a(b|(c|d))' uzorci dok '(a)', 'b|c', 'aab)b' nisu.

Kažemo da lozinka odgovara uzorku ako možemo od uzorka dobiti lozinku nizom koraka gdje u svakom koraku odaberemo jedan podniz uzorka oblika '(u1|u2|...|uk)', takav da nizovi u1, u2, ..., uK ne sadrže zagrade, te ga zamjenimo jednim od nizova u1, u2, ..., uK.

Tako, na primjer, lozinka 'ad' odgovara uzorku 'a(b|(c|d))' jer se može od toga uzorka dobiti u dva koraka 'a(b|(c|d))' → 'a(b|d)' → 'ad'.

Napiši program koji će naći broj različitih lozinki koje odgovaraju zadanom uzorku.

Dakle, ako se neka lozinka može dobiti na dva različita načina, treba je brojati samo jednom.

Ulazni podaci

U prvom i jedinom retku ulaza nalazi se niz od najvše 60 malih slova engleske abecede i znakova zagrada '(', ')' te vertikalne crte '|' (ASCII kôd 124). Ulazni niz predstavlja Mirkov ispravni uzorak.

Izlazni podaci

Potrebno je ispisati jedan prirodni broj - broj različitih lozinki koje odgovaraju zadanom uzorku.

Primjeri test podataka

Ulaz

m(i|a)rko

Izlaz

2

Ulaz

mir(k|ko)(os|s|o)

Izlaz

5