求兩個正規式之間的編輯距離

正規式與編輯距離都是常見知識，如果不熟悉請見原題^[1]

兩個字符串之間的編輯距離的經典解法是動態規劃。然而正規式可能包含無窮多個字符串。 不好將它轉化到兩字符串的編輯距離上。另外一個問題，首先要有一種能夠識別正規式的方法，就像進行表達式計算時，用遞歸下降方法來識別就很順手。

一時之間想不起用什么來表示正規式，后來看到解題報告 ^[2] 才有恍然大悟的感覺，用一個NFA^[3]來表示正規式（編譯原理課上學過的，還是重點）。這樣狀態非常的清晰。

首先將正規式轉換成NFA的形式，這樣兩個正規式，就變成了兩個NFA。設<x , y>表示當前匹配到第一個NFA的x狀態，第二個NFA的y狀態所消耗的當前最少代價。對于當前的狀態<s1, s2>尋找他所有的后繼<t1, t2>，如果發現能夠更新后繼<t1, t2>,那么更新它，并且將它入隊，用于更新其他的狀態。當隊列里空了時候，那么就求到了最小編輯距離。

這里有個小技巧，就是標記當前狀態是否已經在隊列中，防止隊列中出現重復狀態。具體實現可以參考UESTC_Melody的代碼^[4]，寫的非常優美。

引用

[1]http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=5109

[2] http://icpc.amrita.ac.in/2010/images/solution_logic.pdf

[3] http://en.wikipedia.org/wiki/Nondeterministic_finite_state_machine

[4] http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=56951