1398 . Regular Expression Edit Distance

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

A regular expression is used to describe a set of strings. For this problem the alphabet is limited to 'a' and 'b'. R is a regular expression if:



  1. R is "a" or "b"

  2. R is of the form "(R1R2)" where R1 and R2 are regular expressions

  3. R is of the form "(R1|R2)" where R1 and R2 are regular expressions

  4. R is of the form "(R1*)" where R1 is a regular expression.

The set of strings recognised by R are as follows:


  1. If R is "a", then the set of strings recognised = {a}

  2. If R is "b", then the set of strings recognised = {b}

  3. if R is of the form "(R1R2)" then the set of strings recognised = all strings which can be obtained by a concatenation of strings s1 and s2 where s1 is recognised by R1 and s2 by R2.

  4. if R is of the form "(R1|R2)" then the set of strings recognised = union of the set of strings recognised by R1 and R2.

  5. If R is of the form "(R1*)" then the the strings recognised are the empty string and the concatenation of an arbitrary number of copies of any string recognised by R1.

The edit distance between two strings s1 and s2 is the minimum number of characters to 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 amongst all pairs of strings s1 and s2 such that s1 is recognised by R1 and s2 is recognised by R2.

Input Format

The first line contains the number of test cases T. T test cases follow.

Each test case contains two lines containing two regular expressions R1 and R2. There is a blank line after each test case.

T <= 85

1 <= length(R1), length(R2) <= 65

You are guaranteed that R1 and R2 will conform to the definition provided above.

Output Format

Output T lines one corresponding to each test case containing the required answer for the corresponding test case.

Sample Input 1

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

(a((ab)*))
(a(b(((ab)b)b)))

Sample Output 1

0
2

Hints

For the first case R1 recognises all strings over the alphabet a and b. Thus it recognises the string "abaa" which is also recognised by R2.
For the second case the strings "aababab" and "ababbb" are recognised by R1 and R2 respectively and have edit distance of 2.

Problem Source

Migrated from old NTUJ.

Regional Amritapuri 2010

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 200
Submit
Back to Top