SP8056 AMR10B - Regex Edit Distance

在这道题目中，我们使用正则表达式来描述一组字符串。题目限定的字母表是 'a' 和 'b'。一个正则表达式 $R$ 满足以下任一条件时即为合法： 1. $R$ 为 "a" 或 "b" 2. $R$ 可以写成 "(R1R2)" 形式，其中 R1 和 R2 都是正则表达式 3. $R$ 可以写成 "(R1|R2)" 形式，其中 R1 和 R2 都是正则表达式 4. $R$ 可以写成 "(R1*)" 形式，其中 R1 是正则表达式 识别的字符串集合由 $R$ 描述如下： 1. 当 $R$ 为 "a" 时，识别的字符串集合为 {a} 2. 当 $R$ 为 "b" 时，识别的字符串集合为 {b} 3. 若 $R$ 的形式是 "(R1R2)"，识别的字符串集合是所有能由 R1 识别的字符串 s1 和由 R2 识别的字符串 s2 连同起来得到的字符串 4. 若 $R$ 的形式是 "(R1|R2)"，识别的字符串集合是 R1 和 R2 识别集合的并集 5. 若 $R$ 的形式是 "(R1\*)" ，识别的字符串集合包括空字符串以及任意多个 R1 识别的字符串连接起来得到的字符串 字符串 s1 和 s2 之间的编辑距离是指将 s1 通过最少的字符插入、删除或替换操作变成 s2 所需的步数。 给定两个正则表达式 $R1$ 和 $R2$，求在所有由 $R1$ 识别的字符串 s1 和由 $R2$ 识别的字符串 s2 之间的最小编辑距离。

第一行输入一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例。 每个测试用例由两行组成，分别包含一个正则表达式 $R1$ 和 $R2$。每个测试用例之间用一个空行分隔。

输出 $T$ 行，每行对应一个测试用例的最小编辑距离。

- $T \leq 100$ - $1 \leq \text{length}(R1), \text{length}(R2) \leq 50$ - 保证 $R1$ 和 $R2$ 完全符合题目给出的定义。 **样例输入** ``` 2 ((a|b)*) (a(b(aa))) (a((ab)*)) (a(b(((ab)b)b))) ``` **样例输出** ``` 0 2 ``` **解释** - 对于第一个测试用例，$R1$ 能识别所有由 'a' 和 'b' 组成的字符串，因此它也识别字符串 "abaa"，这个字符串同样被 $R2$ 识别。 - 对于第二个测试用例，字符串 "aababab" 和 "ababbb" 分别被 $R1$ 和 $R2$ 识别，而它们之间的编辑距离为 2。 **本翻译由 AI 自动生成**