結果
問題 | 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); //deletedp[i][j+1] = min(dp[i][j+1], dp[i][j]+1); //insertdp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+1); //updateif(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;}