<PREV Problem:
NEXT>
Solved by 165 users: ...
UserDateAttemptTimeCMSC
Tulegenov_Amir03 aug 2007Kylix700.01383 
Tulegenov_Amir30 jul 2007Kylix400.01391 
gleam18 oct 2008C++1300.04402 
DAV21 mar 2009C++300.03414 
Tulegenov_Amir30 jul 2007Kylix300.01425 
Tulegenov_Amir30 jul 2007Kylix200.01448 
DAV18 mar 2009C++200.02452 
DAV18 mar 2009C++100.01483 
Vladislav_Simonenko20 mar 2006FPC300.01497 
best11 apr 2004C++1?.??507 
deepakmanohar11 apr 2004C++1?.??507 
Irioth30 nov 2006Java200.26512 
Tulegenov_Amir02 dec 2007FPC900.01520 
g20151321 apr 2006FPC100.01531 
murphy26 jun 2006FPC100.01531 
Lin18 jan 2004FPC3?.??531 
Languages
C++
91
FPC
39
Kylix
15
Java
13
C
8
Ruby
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Two regular expressions

Time limit = 2 second(s)

You are given two regular expressions R1 and R2 and should find minimal string S matching both. String consists of capital latin letters A..Z. Regular expression is word consisting of A..Z and * ? symbols. The symbol * corresponds to any word or empty word. The symbol ? corresponds to one letter.

Input Two lines with regular expressions R1 and R2, each line has less than 500 characters.

Output String S — one of the strings with minimal length matching both regular expressions. If string matching R1 and R2 does not exist, then output #.

Input#1
?A*BCD
*ABC?
Output#1
AABCD

Input#2
?*A*?
???
Output#2
AAA

Input#3
B*A*A
?B?
Output#3
#

Author:
From the book "National features of programming problems" 29 September 2003

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


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

SW soft NIX
ID = 34.200.222.93