<PREV Problem:
NEXT>
Solved by 363 users: ...
UserDateAttemptTimeCMSC
MaxBuzz23 feb 2009C++2100.01130 
MaxBuzz23 feb 2009C++2300.01130 
MaxBuzz23 feb 2009C++1800.01135 
MaxBuzz23 feb 2009C++1900.01135 
glueray29 oct 2006C++700.02137 
glueray29 oct 2006C++600.01139 
MaxBuzz23 feb 2009C++1600.01143 
glueray29 oct 2006C++500.01144 
zhouxiaobo11 jan 2007FPC100.03149 
Abzal_ktl18 jan 2008Kylix100.01154 
QWE28 oct 2007FPC100.02154 
nrg07 nov 2008FPC100.01155 
pshen23 nov 2010C++1500.02155 
zhangbjb21 mar 2008FPC100.01160 
gdeng19 aug 2008FPC100.01161 
Woland09 may 2010C++900.02161 
Woland10 may 2010C++1100.02161 
Languages
C++
182
FPC
108
C
28
Java
24
Kylix
23
Ruby
2
Lua
1
Python
1
Perl
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 170ms

SW soft NIX
ID = 3.219.167.194