我在一次采访中遇到了这个问题：
给定两个正则表达式，计算它们之间的编辑距离。编辑距离定义为两个正则表达式分别生成的任意两个字符串之间的最小编辑距离。
形式上，我们正在寻找 d(L1,L2) = min { d(x,y) | x from L1, y from L2 } ，其中L1和L2是由两个正则表达式生成的语言。
我在面试中无法解决它。即使是现在，我也不知道如何解决它。有什么想法吗？
我认为这与 http://www.spoj.com/problems/AMR10B/相同
有代表这两种语言的有限状态机。假设第一种语言有状态 S[1]、S[2]、...、S[N1] 和转换 c：S[i]->S[j]（表示状态 i 在输入字符 c 下转到状态 j），以及 T[1]、T[2]、...T[N2] 表示第二语言（具有自己的一组过渡）。
现在，您可以构造加权多图，其中节点是状态对，并且对之间的边（S[i1]，T[i2]）->（S[j1]，T[j2]）如果以下四种情况中的任何一种成立：
- 有 c：S[i1] -> S[j1] 和 i2 = j2。重量为 1
- 有 c：T[i2] -> T[j2] 和 i1 = j1。重量为 1 有 c： S[i1] ->
- S[j1] 和 c： T[i2] -> T[j2]。这有重量 0 有 c： S[i1] ->
- S[j1] 和 d： T[i2] -> T[j2]。重量为 1
然后，找到从一对开始状态到任何一对接受状态的最低权重路径，为您提供最小的编辑距离。