정규 표현식 편집 거리

시간 제한5초메모리 제한1024 MB

요약

알파벳 a와 b로 이루어진 정규 표현식 두 개가 주어졌을 때, 각각이 인식하는 문자열 사이의 최소 편집 거리를 구합니다.

문제

정규 표현식은 문자열의 집합을 나타낸다. 이 문제에서 알파벳은 'a'와 'b'뿐이다. R이 다음 중 하나에 해당하면 R은 정규 표현식이다.

정규 표현식 R이 인식하는 문자열의 집합은 다음과 같다.

R이 "a"이면 인식하는 집합은 {a}이다.
R이 "b"이면 인식하는 집합은 {b}이다.
R이 "(R1R2)" 형태이면, R1이 인식하는 문자열 s1과 R2가 인식하는 문자열 s2를 이어 붙여 만들 수 있는 모든 문자열이 인식하는 집합이다.
R이 "(R1|R2)" 형태이면, R1과 R2가 인식하는 집합의 합집합이다.
R이 "(R1*)" 형태이면, 빈 문자열과 R1이 인식하는 문자열을 임의의 횟수만큼 이어 붙여 만들 수 있는 모든 문자열이 인식하는 집합이다.

두 문자열 s1과 s2의 편집 거리는 s1을 s2와 같게 만들기 위해 삽입, 삭제, 치환해야 하는 문자의 최소 개수이다.

두 정규 표현식 R1과 R2가 주어진다. s1이 R1이 인식하는 문자열이고 s2가 R2가 인식하는 문자열일 때, 가능한 모든 (s1, s2) 쌍 중에서 편집 거리의 최솟값을 구하라.

첫 줄에 테스트 케이스의 개수 T가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어지며, 각 줄에 정규 표현식 R1과 R2가 하나씩 주어진다. 각 테스트 케이스 뒤에는 빈 줄이 있다.

T개의 줄에 답을 출력한다. i번째 줄에는 i번째 테스트 케이스의 답을 출력한다.

T는 85 이하이다.

R1과 R2의 길이는 각각 1 이상 50 이하이다.

입력되는 R1과 R2는 위의 정의를 따르는 것이 보장된다.

첫 번째 경우에서 R1은 a와 b로 이루어진 모든 문자열을 인식한다. 따라서 R1은 "abaa"를 인식하고, 이 문자열은 R2도 인식한다.

두 번째 경우에서 R1과 R2가 각각 인식하는 "aababab"와 "ababbb"의 편집 거리는 2이다.

예제 1

입력

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

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

예상 출력

0
2