結果
問題 | No.874 正規表現間距離 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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_mojiif(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){//?_mojidp[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){//*_mojidp[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;}