Solved by 363 users: ...
<
<
<
<
<
<
<
<
<
<

## Regular expression I

Time limit = 5 second(s)

We have two words W and R. The first W is word to test with letters from the alphabet B={a,b, .. z}. The second R is regular expression with letters from the alphabet B'={*,a,b,..z}.

Each start '*' in regular expression should be treated as subword from the alphabet B (empty substring is possible). Two stars can't go together.

Realization of R in W is substitutions for each '*' that produce W from R.

Your program should count number of different realizations of R in W.

Input. Two lines, the first contains W, the second contains R. Lengths of R and W less than 1000.

Output. One line with integer number. It is known that it less than 2 000 000 000.

 Input#1abcd a*d Output#11
 Input#2abcde a*d Output#20
 Input#3abcdcde a*c*e Output#32
 Input#4abcdefabcdefabcdef *abc*def* Output#46

Author:
Voroztsov Artem, MIPT Contect, February 2003.
16 February 2003

 © acm.mipt DevGroupThe page was generated in 180ms