<PREV Problem:
NEXT>
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#1
abcd
a*d
Output#1
1
Input#2
abcde
a*d
Output#2
0
Input#3
abcdcde
a*c*e
Output#3
2
Input#4
abcdefabcdefabcdef
*abc*def*
Output#4
6

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

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.162.181.75