<ПРЕД Задача:
СЛЕД>
Задачу решили 363 пользователя: ...
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 
Языки
C++
182
FPC
108
C
28
Java
24
Kylix
23
Ruby
2
Lua
1
Python
1
Perl
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Регулярное выражение I

Time limit = 5 секунд(ы)

На вход подаётся слово W в алфавите маленьких латинских букв B={a,b, ... , y, z} и регулярное выражение R . слово в алфавите B'={*, a, b, ... , y, z}. Каждая звездочка в регуляном выражение может означать какое-то слово в алфавите B (в том числе пустое). Две звездочки не могут идти подряд.

Регулярное выражение R реализует слово W, если в R вместо звездочек можно подставить какие-то слова в алфавите B так, что оно превратится в слово W.

Указания, что нужно подставлять вместо каждой конкретной звездочки, назовем реализацией W в R. Сколько существует различных реализаций W в R?

Вход. Вход состоит из двух строчек. В первой строчке записано W, во втрой R. Длины обоих слов меньше 1000.

Выход. Выход должен содержать количество различных реализаций. Известно, что это число меньше 2 000 000 000.

Вход#1
abcd
a*d
Выход#1
1
Вход#2
abcde
a*d
Выход#2
0
Вход#3
abcdcde
a*c*e
Выход#3
2
Вход#4
abcdefabcdefabcdef
*abc*def*
Выход#4
6

Автор:
Ворожцов Артем, Олимпиада МФТИ, февраль 2003.
16 февраля 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


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

SW soft NIX
ID = 54.237.183.249