結果
問題 | No.874 正規表現間距離 |
ユーザー |
![]() |
提出日時 | 2019-09-02 22:04:15 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 1,771 bytes |
コンパイル時間 | 769 ms |
コンパイル使用メモリ | 61,420 KB |
実行使用メモリ | 19,124 KB |
最終ジャッジ日時 | 2024-12-17 18:36:01 |
合計ジャッジ時間 | 2,334 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#include <iostream> #include <string> using namespace std; string s, t; string s1, s2, t1, t2; int dp[2005][2005]; int main(void) { cin >> s >> t; for(int i = 0; i < s.size(); i++){ if(s[i] == '?' || s[i] == '*'){ s1.erase(s1.end()-1); s1 += s[i]; } else s1 += s[i], s2 += s[i]; } for(int i = 0; i < t.size(); i++){ if(t[i] == '?' || t[i] == '*'){ t1.erase(t1.end()-1); t1 += t[i]; } else t1 += t[i], t2 += t[i]; } s = s1, t = t1; int S = s.size(), T = t.size(); s = "#" + s, t = "#" + t; s2 = "#" + s2, t2 = "#" + t2; for(int i = 0; i <= S; i++){ for(int j = 0; j <= T; j++){ dp[i][j] = 1e9; } } dp[0][0] = 0; for(int i = 0; i <= S; i++){ for(int j = 0; j <= T; j++){ if(j == T){ if(i == S) continue; if(s[i+1] == '?' || s[i+1] == '*') dp[i+1][j] = min(dp[i+1][j], dp[i][j]); else dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1); continue; } if(i == S){ if(t[j+1] == '?' || t[j+1] == '*') dp[i][j+1] = min(dp[i][j+1], dp[i][j]); else dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1); continue; } char c = s[i+1], d = t[j+1]; if(c == '?' || c == '*') c = s2[i+1]; if(d == '?' || d == '*') d = t2[j+1]; if(c == d){ dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]); if(s[i+1] == '*') dp[i][j+1] = min(dp[i][j+1], dp[i][j]); if(t[j+1] == '*') dp[i+1][j] = min(dp[i+1][j], dp[i][j]); } dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1); //delete dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1); //insert dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+1); //update if(s[i+1] == '?' || s[i+1] == '*') dp[i+1][j] = min(dp[i+1][j], dp[i][j]); if(t[j+1] == '?' || t[j+1] == '*') dp[i][j+1] = min(dp[i][j+1], dp[i][j]); } } cout << dp[S][T] << endl; return 0; }