問題
3つの文字列S1,S2,S3が与えられる。
2つの文字列s,tの編集距離をd(s,t)とする。
最適なtを選んだ時、d(t,S1)+d(t,S2)+d(t,S3)の最小値はいくつか。
解法
f(a,b,c) := S1,S2,S3の先頭a,b,c文字目まで実現する編集距離がわかっているとき、残りを整えるコスト
とし、f(0,0,0)を求めよう。
f(a,b,c)において取れる選択肢は以下のいずれか。
- S1,S2,S3のいずれかを1文字削除する。すなわちコストを1かけa,b,cをいずれか1すすめる
- S1[a],S2[b],S3[c]のどれか1文字をtに追加する。
- 例えばS1[a]と同じ文字を追加するとき、それがS2[b]やS3[c]と同じなら、bやcをコストなくインクリメントできる。
- そうでない場合は、b・cは、S1[a]をTから削除するためにコスト1かけて継続させるか、コスト1かけて置換し、b・cをインクリメントさせるかどちらか。
int L[3]; string S[3]; int memo[101][101][101]; int dfs(int a,int b,int c) { if(a>L[0]||b>L[1]||c>L[2]) return 101010; if(a==L[0]&&b==L[1]&&c==L[2]) return 0; if(memo[a][b][c]>=0) return memo[a][b][c]; int ret=101010; if(a<L[0]) ret=min(ret,dfs(a+1,b,c)+1); if(b<L[1]) ret=min(ret,dfs(a,b+1,c)+1); if(c<L[2]) ret=min(ret,dfs(a,b,c+1)+1); if(a<L[0]) { int cb=0,cc=0; if(b<L[1]&&S[1][b]!=S[0][a]) cb++; if(c<L[2]&&S[2][c]!=S[0][a]) cc++; ret=min(ret,dfs(a+1,b+1,c+1)+cb+cc); ret=min(ret,dfs(a+1,b+1,c)+cb+1); ret=min(ret,dfs(a+1,b,c+1)+1+cc); ret=min(ret,dfs(a+1,b,c)+2); } if(b<L[1]) { int ca=0,cc=0; if(a<L[0]&&S[0][a]!=S[1][b]) ca++; if(c<L[2]&&S[2][c]!=S[1][b]) cc++; ret=min(ret,dfs(a+1,b+1,c+1)+ca+cc); ret=min(ret,dfs(a+1,b+1,c)+ca+1); ret=min(ret,dfs(a,b+1,c+1)+1+cc); ret=min(ret,dfs(a,b+1,c)+2); } if(c<L[2]) { int ca=0,cb=0; if(a<L[0]&&S[0][a]!=S[2][c]) ca++; if(b<L[1]&&S[1][b]!=S[2][c]) cb++; ret=min(ret,dfs(a+1,b+1,c+1)+ca+cb); ret=min(ret,dfs(a+1,b,c+1)+ca+1); ret=min(ret,dfs(a,b+1,c+1)+1+cb); ret=min(ret,dfs(a,b,c+1)+2); } return memo[a][b][c]=ret; } void solve() { int i,j,k,l,r,x,y; string s; FOR(i,3) { cin>>L[i]>>S[i]; } MINUS(memo); cout<<dfs(0,0,0)<<endl; }
まとめ
やることは明確だけど実装が若干ややこしい。
