编辑两个正则表达式之间的距离

Question

我在接受采访时遇到了这个问题:

给定两个正则表达式,计算它们之间的编辑距离.编辑距离被定义为分别由两个正则表达式生成的任意两个字符串之间的最小编辑距离.

在形式上,我们都在寻找d(L1,L2) = min { d(x,y) | x from L1, y from L2 },在那里L1和L2是由两个正则表达式生成的语言.

在采访中我无法解决这个问题.即使是现在我也没有任何线索如何解决它.有任何想法吗？

我认为这与http://www.spoj.com/problems/AMR10B/相同

Answer 1

有代表这两种语言的有限状态机。假设第一种语言具有状态 S[1]、S[2]、...、S[N1] 和转换 c：S[i]->S[j]（意味着状态 i 在输入字符下转到状态 j c)，以及第二语言的 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

然后，找到从一对开始状态到任意一对接受状态的最低权重路径即可得出最小编辑距离。