PATT - Pattern Matching

A regular expression is a string which contains some normal characters and some meta characters. The meta characters include:

  • . means any character
  • [c1 - c2] means any character between c1 and c2 (c1 and c2 are two characters).
  • [ˆc1 - c2] means any character not between c1 and c2 (c1 and c2 are two characters).
  • * means the character before it can occur any times.
  • + means the character before it can occur any times but at least one times.
  • \ means any character follow should be treated as normal character.

You are to write a program to find the leftmost substring of a given string, so that the substring can match a given regular expression. If there are many substrings of the given string can match the regular expression, and the left positions of these substrings are same, we prefer the longest one.

Input

Every two lines of the input is a pattern-matching problem. The first line is a regular expression, and the second line is the string to be matched. Any line will be no more than 80 character. A line with only an end will terminate the input.

Output

For each matching problem, you should give an answer in one line. This line contains the string to be matched, but the leftmost substring that can match the regular expression should be bracketed. If no substring matches the regular expression, print the input string.

Example

Input:
.*
asdf
f.*d.
sefdfsde
[0-9]+
asd345dsf
[^\*-\*]
**asdf**fasd
b[a-z]*r[s-u]*
abcdefghijklmnopqrstuvwxyz
[T-F]
dfkgjf
end
Output:
(asdf)
se(fdfsde)
asd(345)dsf
**(a)sdf**fasd
a(bcdefghijklmnopqrstu)vwxyz
dfkgjf

Added by:Andres Tellez
Date:2011-05-17
Time limit:5.454s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2011-05-18 07:40:42 Johannes Laire
But the example input has [T-F].
2011-05-18 05:33:17 Oleg
[T-F] is not valid regexp.
2011-05-17 22:28:00 Johannes Laire
More test cases for various corner cases or a more exact definition of the input would be nice. Some questions:

Is [T-F] equal to [F-T] or is it an empty range?
Can the pattern include non-matching square brackets?
Can the last character be a lonely backslash? In other words, is \ alone a valid pattern?
Can the first character be + or *?
Edit:
Does [.] match any character or only the dot?
Edit 2:
Can the pattern include nested quantifiers such as *+*++ and what do they mean?
Can the pattern include \M or other pointless escapes?
Which characters are "normal"?
Is [] legal?

Last edit: 2011-05-26 19:00:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.