Subword

Special Judge Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      Let us introduce the free group with two non-commuting generators.
      We will denote generators as a and b and their reverses as A and B respectively. The group can be described as a set of words consisting of a, b, A and B, the operation of concatentation, and the generating relations aA = Aa = Bb = bB = ε.
      In other words, we say that two words are equivalent if one can be transformed to another by successively performing the following operations:
  • remove a subword equal to Aa, aA, Bb or bB from any position;
  • add a subword equal to Aa, aA, Bb or bB to any position.

      For example, words abAaBBabbA and aAaBabaAbA are equivalent:

abAaBBabbA → abBBabbA → aBabbA → aAaBabbA → aAaBabaAbA;

      but words abAB and baBA are not.
      Equivalence classes of words are exactly the elements of the group.
      It is interesting to note that for each word α and each word β there is such word γ equivalent to that α contains β as a subword. Your task in this problem is to find the shortest such word

Input

      The first line of the input file contains α. The second line contains β. Both words are not empty and contain at most 2000 characters each.

Output

      Output one word — the shortest word equivalent to that contains as a subword. If there are several solutions, print any one.

Sample Input

abAaBBabbA
AaBaba

Sample Output

aAaBabaAbA

Hint

单组数据

Source

Andrew Stankevich Contest 16

Manager

Information
Solved Number3
Submit Number19
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel