- #include<bits/stdc++.h>
- #define f2(i, m) for(long long i=0; i<m; i++)
- #define f3(i, n, m) for(long long i=n; i<m; i++)
- #define ll long long
- #define pb push_back
- #define pob pop_back
- #define len length()
- #define elif else if
- #define mod 1000000007
- #define debug
- /*
- #ifdef debug
- #endif
- #ifndef debug
- #endif
- */
- using namespace std;
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- string a, b;
- cin >> a >> b;
- vector <vector <int>> dp(a.len+1, vector <int> (b.len+1));
- dp[0][0] = 0;
- dp[0][1] = 1;
- dp[1][0] = 1;
- f2(i, a.len)
- {
- f2(j, b.len)
- {
- if(a[i]==b[j])
- dp[i][j]=dp[i-1][j-1]+1;
- else
- {
- int x=dp[i-1][j-1],
- y=dp[i-1][j],
- z=dp[i][j-1];
- dp[i+1][j+1] = min(x, min(y, z));
- }
- }
- }
- cout << dp[a.len][b.len];
- return 0;
- }
複製代碼 |