Posted on 2011-01-11 16:21
王之昊 閱讀(475)
評論(0) 編輯 收藏 引用 所屬分類:
字符串
求兩個正規式之間的編輯距離
正規式與編輯距離都是常見知識，如果不熟悉請見原題[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