test/Levenshtein.test.cpp

• View this file on GitHub
• Last update: 2021-03-21 09:59:09+09:00
• Problem: https://yukicoder.me/problems/no/225

Depends on

• DP/Levenshtein.cpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/225"
#include "./../DP/Levenshtein.cpp"
#include <iostream>
#include <string>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n, m;
	string s, t;
	cin >> n >> m >> s >> t;
	cout << Levenshtein(s, t) << '\n';
}

#line 1 "test/Levenshtein.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/225"
#line 2 "DP/Levenshtein.cpp"
#include <vector>
#include <string>
#include <algorithm>

int Levenshtein(const std::string& s, const std::string& t) {
	int S = s.size(), T = t.size();
	std::vector dp(S + 1, std::vector<int>(T + 1));
	for (int i = 0; i <= S; i++) dp[i][0] = i;
	for (int i = 0; i <= T; i++) dp[0][i] = i;
	for (int i = 1; i <= S; i++)
		for (int j = 1; j <= T; j++)
			dp[i][j] = std::min({dp[i - 1][j] + 1, dp[i][j - 1] + 1,
			                dp[i - 1][j - 1] + (s[i - 1] != t[j - 1])});
	return dp[S][T];
}
#line 3 "test/Levenshtein.test.cpp"
#include <iostream>
#line 5 "test/Levenshtein.test.cpp"
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int n, m;
	string s, t;
	cin >> n >> m >> s >> t;
	cout << Levenshtein(s, t) << '\n';
}

Back to top page