結果

問題 No.874 正規表現間距離
ユーザー pockyny
提出日時 2019-05-01 12:40:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,829 bytes
コンパイル時間 1,053 ms
コンパイル使用メモリ 89,448 KB
最終ジャッジ日時 2025-01-07 03:18:15
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 28 WA * 2 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string A,B;
int dp[2010][2010];
int bit(string s,int i){
if(s[i]=='*') return 2;
if(s[i]=='?') return 1;
return 0;
}
int ch(int i, int j){
return 3*bit(A,i) + bit(B,j);
}
int main(){
int i,j,n,m;
cin >> A >> B;
n = A.size(); m = B.size();
for(i=0;i<=n;i++){
for(j=0;j<=m;j++){
dp[i][j] = 100000;
}
}
dp[0][0] = 0;
for(i=1;i<=m;i++){
dp[0][i] = dp[0][i-1] + 1;
if(B[i-1]=='?' || B[i-1]=='*') dp[0][i]--;
}
for(i=1;i<=n;i++){
dp[i][0] = dp[i-1][0] + 1;
if(A[i-1]=='?' || A[i-1]=='*') dp[i][0]--;
}
dp[0][0] = 0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(ch(i-1,j-1)==0){//moji_moji
if(A[i-1]==B[j-1]){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = min(dp[i][j],min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]}) + 1);
}
}
if(ch(i-1,j-1)==1){//moji_?
dp[i][j] = min({dp[i][j],dp[i][j-1],dp[i][j-2]});
}
if(ch(i-1,j-1)==2){//moji_*
dp[i][j] = min({dp[i][j],dp[i][j-2],dp[i][j-1],dp[i-1][j] + (A[i-1]!=B[j-2])});
}
if(ch(i-1,j-1)==3){//?_moji
dp[i][j] = min({dp[i][j],dp[i-1][j],dp[i-2][j]});
}
if(ch(i-1,j-1)==4){//?_?
dp[i][j] = min({dp[i][j],dp[i-1][j-1],dp[i-2][j-1],dp[i-1][j-2],dp[i-2][j-2]});
}
if(ch(i-1,j-1)==5){//?_*
dp[i][j] = min({dp[i][j],dp[i-1][j],dp[i-2][j]});
}
if(ch(i-1,j-1)==6){//*_moji
dp[i][j] = min({dp[i][j],dp[i-2][j],dp[i-1][j],dp[i][j-1] + (A[i-2]!=B[j-1])});
}
if(ch(i-1,j-1)==7){//*_?
dp[i][j] = min({dp[i][j],dp[i][j-1],dp[i][j-2]});
}
if(ch(i-1,j-1)==8){//*_*
dp[i][j] = min({dp[i-2][j-2],dp[i-2][j-1],dp[i-1][j-2],dp[i-1][j-1],dp[i][j-1],dp[i-1][j],dp[i][j]});
}
}
}
/*for(i=0;i<=n;i++){
for(j=0;j<=m;j++){
cout << dp[i][j] << " ";
}
cout << endl;
}*/
cout << dp[n][m] << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0