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

2018-06-08 14:51:23

我在采访中遇到了这个问题：

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

形式上，我们正在寻找d(L1,L2) = min { d(x,y) | x from L1, y from L2 } 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在输入字符下进入状态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

然后，找到从这对开始状态到任何一对接受状态的最低权重路径，都可以为您提供最小的编辑距离。

链接地址: http://www.djcxy.com/p/26045.html