Edit Distance

Edit Distance

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	int editDistDp(string &x, string &y)
	{
	int m = x.length();
	int n = y.length();
	int dp[m + 1][n + 1];
	for (int i = 0; i <= m; i++) {
	for (int j = 0; j <= n; j++) {
	if (i == 0 || j == 0) dp[i][j] = 0;
	else if (x[i - 1] == y[j - 1])
	dp[i][j] = dp[i - 1][j - 1] + 1;
	else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
	}
	}
	int lcs = dp[m][n];
	//dbg(lcs);
	// delete operation + insert operation
	return (m - lcs) + (n - lcs);
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	string s1 = "sunday";
	string s2 = "saturday";
	//string s1 = "abc";
	//string s2 = "acd";
	cout << editDistDp(s1, s2) << endl;
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}
	}

view raw Edit distance and LCS.cpp hosted with ❤ by GitHub

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	int MIN(int x, int y, int z)
	{
	return min(min(x, y), z);
	}
	int editDist(string s, string t, int m, int n)
	{
	if (m == 0) return n;
	if (n == 0) return m;
	if (s[m - 1] == t[n - 1]) return editDist(s, t, m - 1, n - 1);
	return 1 + MIN(editDist(s, t, m, n - 1),// insert
	editDist(s, t, m - 1, n), // remove
	editDist(s, t, m - 1, n - 1) // replace
	);
	}
	///topdownDP
	int dp[100][1000];
	int editDistTopDown(string s, string t, int m, int n)
	{
	if (m == 0) return n;
	if (n == 0) return m;
	if (dp[m - 1][n - 1] != -1)
	return dp[m - 1][n - 1];
	if (s[m - 1] == t[n - 1]) return editDist(s, t, m - 1, n - 1);
	return dp[m - 1][n - 1] = 1 + MIN(editDist(s, t, m, n - 1),// insert
	editDist(s, t, m - 1, n), // remove
	editDist(s, t, m - 1, n - 1) // replace
	);
	}
	/// bottomUp dp --> O(m*n)
	int editDistDp(string s, string t, int m, int n)
	{
	int dp[m + 1][n + 1];
	for (int i = 0; i <= m; i++) {
	for (int j = 0; j <= n; j++) {
	if (i == 0) dp[i][j] = j;
	else if (j == 0) dp[i][j] = i;
	else if (s[i - 1] == t[j - 1])
	dp[i][j] = dp[i - 1][j - 1];
	else {
	dp[i][j] = 1 + MIN(dp[i][j - 1], // insert
	dp[i - 1][j], // romove;
	dp[i - 1][j - 1]);
	}
	}
	}
	return dp[m][n];
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	string s1 = "sunday";
	string s2 = "saturday";
	cout << editDist(s1, s2, (int)s1.length(), (int)s2.length()) << endl;
	cout << editDistDp(s1, s2, (int)s1.length(), (int)s2.length()) << endl;
	memset(dp, -1, sizeof dp);
	cout << editDistDp(s1, s2, (int)s1.length(), (int)s2.length()) << endl;
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}
	}

view raw EditDistance.cpp hosted with ❤ by GitHub

	///https://cses.fi/problemset/task/1639/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	int main()
	{
	FASTIO
	/*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	string a, b;
	cin >> a >> b;
	int n = a.size();
	int m = b.size();
	vector<vector<int> > dp(n + 1, vector<int> (m + 1, 1e9));
	dp[0][0] = 0;
	for (int i = 0; i <= n; i++) {
	for (int j = 0; j <= m; j++) {
	if (i) {
	dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
	}
	if (j) {
	dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
	}
	if (i && j) {
	dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]));
	}
	}
	}
	cout << dp[n][m] << endl;
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw EditDistance1.cpp hosted with ❤ by GitHub

Share: