編輯距離問(wèn)題

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

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

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

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

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

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

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

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

舉一個(gè)例子：a的長(zhǎng)度la=9，b的長(zhǎng)度lb=15

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

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

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

6動(dòng)態(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動(dòng)態(tài)轉(zhuǎn)移方程的推導(dǎo)我們把上面的幾種情況繪成表格：

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

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

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

若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對(duì)于方程②

若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ù)組長(zhǎng)度}{存放字符串，string型存不到1萬(wàn)}{動(dòng)態(tài)規(guī)劃二維表}{a、b字符串}{動(dòng)規(guī)二維表}{la、lb字符串長(zhǎng)度，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：臨時(shí)變量}{這三行是處理邊界問(wèn)題}{找最小}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：臨時(shí)變量}{處理邊界問(wèn)題}{處理注意事項(xiàng)}13程序主體la:=0;lb:=0;repeatinc(la);read(a[la]);untileoln;readln(b[1]);repeatinc(lb);read(b[lb]);untileoln;forj:=1toladofork:=1tolbd