Under construction

Still being built. Things may change

Regular Expression Edit Distance

Time limit5sMemory limit1024 MB

Summary
Given two regular expressions over a and b, find the minimum edit distance between any string matched by the first and any string matched by the second.
Level

Hard8 of 10

Topics
Dynamic programming, Recursion, String
Solved
No attempts yet

問題

A regular expression describes a set of strings. In this problem the alphabet is only 'a' and 'b'. R is a regular expression if it matches one of the following:

  1. R is "a" or "b".
  2. R has the form "(R1R2)", where R1 and R2 are regular expressions.
  3. R has the form "(R1|R2)", where R1 and R2 are regular expressions.
  4. R has the form "(R1*)", where R1 is a regular expression.

The set of strings recognised by R is defined as follows.

  1. If R is "a", the recognised set is {a}.
  2. If R is "b", the recognised set is {b}.
  3. If R has the form "(R1R2)", the recognised set is every string formed by concatenating a string s1 recognised by R1 with a string s2 recognised by R2.
  4. If R has the form "(R1|R2)", the recognised set is the union of the sets recognised by R1 and R2.
  5. If R has the form "(R1*)", the recognised set is the empty string together with every string formed by concatenating any number of copies of strings recognised by R1.

The edit distance between two strings s1 and s2 is the minimum number of characters that must be inserted, deleted, or replaced in s1 to make it equal to s2.

Given two regular expressions R1 and R2, find the minimum edit distance over all pairs of strings where s1 is recognised by R1 and s2 is recognised by R2.

Input

The first line contains the number of test cases T. Each of the T test cases follows. A test case consists of two lines, each containing one regular expression, R1 and R2. There is a blank line after each test case.

Output

Output T lines. Line i contains the answer for test case i.

Constraints

T is at most 85.

1 is at most length(R1) and length(R2), and both are at most 50.

R1 and R2 are guaranteed to follow the definition above.

Hint

In the first case, R1 recognises all strings over the alphabet a and b. So it recognises "abaa", which is also recognised by R2.

In the second case, the strings "aababab" and "ababbb" are recognised by R1 and R2 respectively, and their edit distance is 2.

Examples1

  1. Example 1

    Input
    2
((a|b)*)
(a(b(aa)))

(a((ab)*))
(a(b(((ab)b)b)))
    Expected output
    0
2