結果
問題 | No.874 正規表現間距離 |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:54:36 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 1,718 bytes |
コンパイル時間 | 899 ms |
コンパイル使用メモリ | 101,384 KB |
実行使用メモリ | 19,584 KB |
最終ジャッジ日時 | 2024-11-22 02:01:34 |
合計ジャッジ時間 | 2,772 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;int main(){string a, b; cin>>a>>b;int n=a.size(), m=b.size();int dp[2020][2020];dp[0][0]=0;for(int i=0; i<n; i++){if(!('a'<=a[i] && a[i]<='z')){dp[i+1][0]=dp[i][0];continue;}if(i+1<n && !('a'<=a[i+1] && a[i+1]<='z')) dp[i+1][0]=dp[i][0];else dp[i+1][0]=dp[i][0]+1;}for(int i=0; i<m; i++){if(!('a'<=b[i] && b[i]<='z')){dp[0][i+1]=dp[0][i];continue;}if(i+1<m && !('a'<=b[i+1] && b[i+1]<='z')) dp[0][i+1]=dp[0][i];else dp[0][i+1]=dp[0][i]+1;}for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(!('a'<=a[i] && a[i]<='z')){dp[i+1][j+1]=dp[i][j+1];continue;}if(!('a'<=b[j] && b[j]<='z')){dp[i+1][j+1]=dp[i+1][j];continue;}dp[i+1][j+1]=min({dp[i][j+1]+1, dp[i+1][j]+1, dp[i][j]+1});if(a[i]==b[j]) dp[i+1][j+1]=min(dp[i+1][j+1], dp[i][j]);if(i+1<n && !('a'<=a[i+1] && a[i+1]<='z')) dp[i+1][j+1]=min(dp[i+1][j+1], dp[i][j+1]);if(j+1<m && !('a'<=b[j+1] && b[j+1]<='z')) dp[i+1][j+1]=min(dp[i+1][j+1], dp[i+1][j]);if(i+1<n && a[i+1]=='*' && a[i]==b[j]) dp[i+1][j+1]=min(dp[i+1][j+1], dp[i+1][j]);if(j+1<m && b[j+1]=='*' && a[i]==b[j]) dp[i+1][j+1]=min(dp[i+1][j+1], dp[i][j+1]);}}cout<<dp[n][m]<<endl;return 0;}