結果
問題 | No.874 正規表現間距離 |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:46:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 2,820 bytes |
コンパイル時間 | 1,355 ms |
コンパイル使用メモリ | 111,808 KB |
実行使用メモリ | 19,192 KB |
最終ジャッジ日時 | 2024-11-22 01:42:19 |
合計ジャッジ時間 | 2,565 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#include<iostream>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<cassert>using namespace std;//#define int long longtypedef long long ll;typedef unsigned long long ul;typedef unsigned int ui;const ll mod = 1000000007;const ll INF = mod * mod;typedef pair<int, int> P;#define stop char nyaa;cin>>nyaa;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)typedef pair<ll, ll> LP;typedef vector<ll> vec;typedef long double ld;typedef pair<ld, ld> LDP;const ld eps = 1e-5;int dp[2001][2001];int atype[2001];int btype[2001];void solve() {string a, b; cin >> a >> b;string nexa, nexb;rep(i, a.size()) {if (a[i] == '?') {atype[nexa.size() - 1] = 1;}else if (a[i] == '*') {atype[nexa.size() - 1] = 2;}else {nexa.push_back(a[i]);}}rep(i, b.size()) {if (b[i] == '?') {btype[nexb.size() - 1] = 1;}else if (b[i] == '*') {btype[nexb.size() - 1] = 2;}else {nexb.push_back(b[i]);}}a = nexa, b = nexb;int n = a.size(), m = b.size();rep(i, n + 1) {rep(j, m + 1) {dp[i][j] = mod;}}dp[0][0] = 0;rep(i, n+1) {rep(j, m+1) {if (i == n) {if (j == m)continue;if (btype[j] > 0)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);}else if (j == m) {if (atype[i] > 0)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);}else {//いつものdp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1);dp[i + 1][j+1] = min(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]);//i飛ばすif (atype[i] > 0) {dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);}//j飛ばすif (btype[j] > 0) {dp[i][j + 1] = min(dp[i][j + 1],dp[i][j]);}if (a[i] == b[j]) {//jは進んでiは残るif (atype[i] == 2) {dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);}//iは進んでjは残るif (btype[j] == 2) {dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);}}}}}//cout << a << " "<<b << endl;cout << dp[n][m] << endl;}signed main() {ios::sync_with_stdio(false);cin.tie(0);//cout << fixed << setprecision(5);//init();solve();//cout << "finish" << endl;//stopreturn 0;}