El Judge
| Online MIPT programming contest | РУССКИЙ |
| <PREV Problem: | NEXT> |
< |
|---|
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 DevGroup The page was generated in 230ms |
