シンプルな設定で良かった。
https://yukicoder.me/problems/no/874
問題
アルファベット・"?"・"*"で構成される2つの正規表現が与えられる。
各正規表現に対応する文字列を1個ずつ選んだ時、編集距離の最小値を求めよ。
解法
正規表現に対し、編集距離と似たDPなりメモ化再帰を行えばよい。
ただ、"?"のついた表現はマッチする文字が無くても文字列のindexを進めることができ、"*"のついた表現は、加えてマッチしても文字列のindexを進めず留め置くことができる点に注意。
string A,B; vector<pair<char,int>> X,Y; int N,M; int memo[4040][4040]; vector<pair<char,int>> conv(string S) { vector<pair<char,int>> R; int i=0; while(i<S.size()) { if(i+1<S.size()&&S[i+1]=='?') { R.push_back({S[i],0}); i+=2; } else if(i+1<S.size()&&S[i+1]=='*') { R.push_back({S[i],2}); i+=2; } else { R.push_back({S[i],1}); i++; } } //FORR(r,R) cout<<(char)r.first<<r.second<<" "; //cout<<endl; return R; } int hoge(int x,int y) { if(memo[x][y]>=0) return memo[x][y]; if(x==N&&y==M) return 0; int ret=1<<30; if(x==N) { ret=(Y[y].second==1)+hoge(x,y+1); } else if(y==M) { ret=(X[x].second==1)+hoge(x+1,y); } else { ret=min(ret,1+hoge(x+1,y+1)); ret=min(ret,1+hoge(x+1,y)); ret=min(ret,1+hoge(x,y+1)); if(X[x].second==0||X[x].second==2) ret=min(ret,hoge(x+1,y)); if(Y[y].second==0||Y[y].second==2) ret=min(ret,hoge(x,y+1)); if(X[x].first==Y[y].first) { ret=min(ret,hoge(x+1,y+1)); if(Y[y].second==2) ret=min(ret,hoge(x+1,y)); if(X[x].second==2) ret=min(ret,hoge(x,y+1)); } } //cout<<x<<y<<" "<<ret<<endl; return memo[x][y]=ret; } void solve() { int i,j,k,l,r,x,y; string s; cin>>A>>B; X=conv(A); Y=conv(B); N=X.size(); M=Y.size(); MINUS(memo); cout<<hoge(0,0)<<endl; }
まとめ
何を勘違いしたか、最初"*"を"+"と間違えて解いてしまった。
その方が若干テクニカルで面白いかもね。
まぁ"x+"→"xx*"と置き換えればあとは同じだけど…。