Problem 1 Compute the optimal alignment of strings 1221 and 2132 given a cost fu

Question

Problem 1 Compute the optimal alignment of strings 1221 and 2132 given a cost function defined such that d(ni,-)-n d(-, nj) = nj That is, the cost of deleting or inserting a symbol is equal to its value, and the cost of substituting one symbol for another is equal to the absolute difference in their values. For example, d(2, 1)-1, d(1,3)-2, and d(-,4)-4 Fill out the graph-looking dynamic programming matrix to the left with the optimal alignment costs and mark the corresponding link information on the graph-looking matrix to the right. When done, use backtracking to extract all possible alignments of the two strings.

Explanation / Answer

Code

#include <algorithm>

#include <bitset>

#include <cassert>

#include <climits>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <deque>

#include <iomanip>

#include <iostream>

#include <map>

#include <numeric>

#include <queue>

#include <set>

#include <stack>

#include <string>

#ifdef PRINTERS

#include "printers.hpp"

using namespace printers;

#define tr(a) cerr<<#a<<" : "<<a<<endl;

#else

#define tr(a)

#endif

#define ll long long

#define pb push_back

#define mp make_pair

#define pii pair<int,int>

#define vi vector<int>

#define all(a) (a).begin(),(a).end()

#define F first

#define S second

#define sz(x) (int)x.size()

#define hell 1000000007

#define endl ' '

#define rep(i,a,b) for(int i=a;i<b;i++)

#define rep1(i,b) for(int i=1;i<=b;i++)

using namespace std;

#define MAXN 1000005

int dp[1000][1000];

int min(int x, int y, int z)

{

return min(min(x, y), z);

}

int fn(string s1,string s2,int n,int m){

for(int i=0;i<=n;i++)

{

for(int j=0;j<=m;j++)

{

if(i==0)

dp[i][j] =j;

else if(j==0)

dp[i][j] =i;

else if(s1[i-1]==s2[j-1])

dp[i][j]=dp[i-1][j-1];

else

dp[i][j] =1 + min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]);

}

}

int ans =dp[n][m];

}

void solve()

{

string s1,s2;

int n,m;

cin>>n>>m;

cin>>s1>>s2;

int ans=fn(s1,s2,n,m);

cout<<ans<<endl;

}

int main(){

ios_base::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

int t=1;

//cin>>t;

while(t--){

solve();

}

return 0;

}

Ans =3

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.