<ПРЕД Задача:
СЛЕД>
Задачу решили 363 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Регулярное выражение 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 200ms

SW soft NIX
ID = 34.204.187.106