求兩個(gè)正規(guī)式之間的編輯距離

正規(guī)式與編輯距離都是常見(jiàn)知識(shí)，如果不熟悉請(qǐng)見(jiàn)原題^[1]

兩個(gè)字符串之間的編輯距離的經(jīng)典解法是動(dòng)態(tài)規(guī)劃。然而正規(guī)式可能包含無(wú)窮多個(gè)字符串。 不好將它轉(zhuǎn)化到兩字符串的編輯距離上。另外一個(gè)問(wèn)題，首先要有一種能夠識(shí)別正規(guī)式的方法，就像進(jìn)行表達(dá)式計(jì)算時(shí)，用遞歸下降方法來(lái)識(shí)別就很順手。

一時(shí)之間想不起用什么來(lái)表示正規(guī)式，后來(lái)看到解題報(bào)告 ^[2] 才有恍然大悟的感覺(jué)，用一個(gè)NFA^[3]來(lái)表示正規(guī)式（編譯原理課上學(xué)過(guò)的，還是重點(diǎn)）。這樣狀態(tài)非常的清晰。

首先將正規(guī)式轉(zhuǎn)換成NFA的形式，這樣兩個(gè)正規(guī)式，就變成了兩個(gè)NFA。設(shè)<x , y>表示當(dāng)前匹配到第一個(gè)NFA的x狀態(tài)，第二個(gè)NFA的y狀態(tài)所消耗的當(dāng)前最少代價(jià)。對(duì)于當(dāng)前的狀態(tài)<s1, s2>尋找他所有的后繼<t1, t2>，如果發(fā)現(xiàn)能夠更新后繼<t1, t2>,那么更新它，并且將它入隊(duì)，用于更新其他的狀態(tài)。當(dāng)隊(duì)列里空了時(shí)候，那么就求到了最小編輯距離。

這里有個(gè)小技巧，就是標(biāo)記當(dāng)前狀態(tài)是否已經(jīng)在隊(duì)列中，防止隊(duì)列中出現(xiàn)重復(fù)狀態(tài)。具體實(shí)現(xiàn)可以參考UESTC_Melody的代碼^[4]，寫(xiě)的非常優(yōu)美。

引用

[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