編輯距離問題

編輯距離問題1題目描述假設(shè)字符串的基本操作僅為：刪除一個字符、插入一個字符和將一個字符修改成另一個字符這三種操作。

我們把進(jìn)行了一次上述三種操作的任意一種操作稱為進(jìn)行了一步字符基本操作。

下面我們定義兩個字符串的編輯距離：對于兩個字符串a(chǎn)和b，通過上述的基本操作，我們可以把a變成b或b變成a，那么字符串a(chǎn)變成字符串b需要的最少基本字符操作步數(shù)稱為字符串a(chǎn)和字符串b的編輯距離。

例如：a=“ABC”,b=“CBCD”,則a與b的編輯距離為2。

你的任務(wù)就是：編寫一個快速的程序來計算任意兩個字符串的編輯距離。輸入輸入包含兩行：第一行為字符串A，第二行為字符串B。

字符串的長度不大于10000，且全為字母。輸出輸出只有一行，為編輯距離。樣例輸入ABC

CBCD樣例輸出22題目分析乍一看仿佛是搜索，但仔細(xì)一想，這道題用搜索是不可能實現(xiàn)的（至少我是這么認(rèn)為的）。那么我們就要采取新的策略：動態(tài)規(guī)劃。我們知道，所有的動規(guī)問題都是可以分段解決的，那么這道題也是如此。我們可以把長的字符串拆解為短的字符串，一直拆解到只剩下一個字符為止。3動態(tài)轉(zhuǎn)移方程的推導(dǎo)判斷啊a、b兩個字符的編輯距離十分簡單：若a=b則編輯距離為0；反之則為1計算字符a與長度為二的字符串b的編輯距離也不難：首先計算a與b[1]的編輯距離，記為f，再判斷a與b[2]是否相同，相同則最終編輯距離為f，不同則為f+1。若b的長度大于2，則該規(guī)律依然成立。

注意：這里出現(xiàn)問題了：假如a=‘a(chǎn)’，b=‘a(chǎn)a’，則它們的編輯距離應(yīng)為1，但通過上述計算得到的結(jié)果為0。4注意這里我們要明確一點，對于任意兩字符串a(chǎn)、b，它們的編輯距離不可能小于它們的長度之差的絕對值。因為對于三種基本操作，它們對字符串長度的影響為±1（插入和刪除）或0（修改）。

舉一個例子：a的長度la=9，b的長度lb=15

則a、b的編輯距離m≥abs(la-lb)

即m≥65動態(tài)轉(zhuǎn)移方程的推導(dǎo)解決了上面一個問題，我們繼續(xù)。

剛才我們已經(jīng)分析出了兩個字符的編輯距離和一個字符與一個字符串的編輯距離，接下來便是兩個字符串的編輯距離。假如a=‘a(chǎn)b’，b=‘cd’，則一眼就可以看出編輯距離m=2。這是沒有重復(fù)字母的情況下。但是如果有重復(fù)字母呢？

6動態(tài)轉(zhuǎn)移方程的推導(dǎo)若a=‘a(chǎn)b’，b=‘bc’，則它們的編輯距離m=2若a=‘a(chǎn)b’，b=‘cb’，則它們的編輯距離m=1若a=‘a(chǎn)b’，b=‘a(chǎn)b’，則它們的編輯距離m=0若a=‘a(chǎn)bc’，b=‘cba’，則它們的編輯距離m=2若a=‘a(chǎn)bc’，b=‘cab’，則它們的編輯距離m=2若a=‘a(chǎn)bc’，b=‘bac’，則它們的編輯距離m=2若a=‘a(chǎn)bc’，b=‘bcd’，則它們的編輯距離m=2這有什么規(guī)律呢？7動態(tài)轉(zhuǎn)移方程的推導(dǎo)我們把上面的幾種情況繪成表格：

8動態(tài)轉(zhuǎn)移方程通過觀察表格我們可以發(fā)現(xiàn)以下規(guī)律：對于表格f，f[j,k]表示a的前j個字符到b的前k個字符的編輯距離①若a[j]≠b[k]

則f[j,k]為f[j-1,k-1]、f[j-1,k]、f[j,k-1]三個數(shù)中最小數(shù)+1②若a[j]=b[k]

則f[j,k]=f[j-1,k-1]最終結(jié)果為f[la,lb]（la、lb為字符串長度）9邊界問題對于方程①

若j=1且k≠1則f[j,k]=f[j,k-1]+1

若k=1且j≠1則f[j,k]=f[j-1,k]+1

若j=1且k=1則f[1,1]=1對于方程②

若j=1且k≠1則f[j,k]=f[j,k-1]

若k=1且j≠1則f[j,k]=f[j-1,k]

若k=1且j=1則f[1,1]=010程序設(shè)定programbjjl;consti_f='bjjl.in';o_f='bjjl.out';maxx=10000;typesz=array[1..maxx]ofchar;dt=array[1..maxx,1..maxx]ofinteger;vara,b:sz;f:dt;la,lb,j,k:integer;{數(shù)組長度}{存放字符串，string型存不到1萬}{動態(tài)規(guī)劃二維表}{a、b字符串}{動規(guī)二維表}{la、lb字符串長度，j、k循環(huán)控制變量}11min函數(shù)functionmin:integer;vart:integer;beginif(j=1)and(k=1)thenmin:=0elseifj=1thenmin:=f[j,k-1]elseifk=1thenmin:=f[j-1,k]elsebeginiff[j-1,k]>f[j,k-1]thent:=f[j,k-1]elset:=f[j-1,k];iff[j-1,k-1]<tthenmin:=f[j-1,k-1]elsemin:=t;end;end;{用于方程①}{t：臨時變量}{這三行是處理邊界問題}{找最小}12fid函數(shù)functionfid:integer;vart:integer;beginif(j=1)and(k=1)thent:=0elseifj=1thent:=f[j,k-1]elseifk=1thent:=f[j-1,k]elset:=f[j-1,k-1];ift<abs(j-k)thenfid:=abs(j-k)elsefid:=t;end;{用于方程②}{t：臨時變量}{處理邊界問題}{處理注意事項}13程序主體la:=0;lb:=0;repeatinc(la);read(a[la]);untileoln;readln(b[1]);repeatinc(lb);read(b[lb]);untileoln;forj:=1toladofork:=1tolbd