시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 64 | 18 | 12 | 24.000% |
Mark is developing new social network Facepalm for inhabitants of Phobos and Deimos. His recent task is to add information about home asteroid of the owner to each account. Of course, each account owner could enter such information, but Mark decided that it would be more convenient if some default value was suggested to the user at logon. He investigated the situation and found out that home asteroid of a user can be found by analyzing his last name.
Last name of each user of Facepalm is a non-empty word consisting of lowercase letters of the English alphabet. Users from Phobos have their last names matching regular expression P while users from Deimos have their last names matching regular expression D.
However, the problem is that some last names can match both expressions. Two expressions are called disjoint if there is no such non-empty string s that matches both expressions. Mark believes that expressions P and D are disjoint. However he needs your help to check it.
You are given two regular expressions P and D. Check whether they are disjoint, and if they are not, find the shortest non-empty string s that matches both of them. If there are several shortest common strings, you can find any one.
The input file contains two lines. The first line contains regular expression P. The second line contains regular expression D. Each expression contains from 1 to 100 characters.
If Mark’s guess is correct and the two expressions are indeed disjoint, print “Correct” at the first line of the output file. If they are not, print “Wrong” at the first line of the output file. In this case the second line must contain any shortest non-empty string that matches both expressions.
a(ab)*b a(a|b)*ab
Correct
a(ab)*a a(a|b)*ba
Wrong aaba
Let us define regular expressions and matching strings to them formally.
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2012 D번