levenshtein_distance(編集距離) (dp/levenshtein_distance.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-06 03:54:40+09:00

なにこれ

レーベンシュタイン距離（編集距離）を求める．

関数

• levenshtein(s1, s2)：文字列 s1 と s2 の編集距離を返す．
• levenshtein(v1, v2)：配列 v1 と v2 の編集距離を返す．

計算量

s1 の長さ（v1 の要素数）を $n$ ，s2 の長さ（v2 の要素数）を $m$ とする．

• $O(nm)$

Verified with

• test/aoj_DPL_1_E.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

int levenshtein(const string &s1, const string &s2) {
	if(s1.length() == 0) return s2.length();
	if(s2.length() == 0) return s1.length();

	vector<vector<int>> dist(s1.length() + 1, vector<int>(s2.length() + 1, (1 << 30) - 1));

	for(int i = 0; i <= s1.length(); i++) dist[i][0] = i;
	for(int i = 1; i <= s2.length(); i++) dist[0][i] = i;
	for(int i = 1; i <= s1.length(); i++)
		for(int j = 1; j <= s2.length(); j++) {
			dist[i][j] = min({dist[i - 1][j] + 1, dist[i][j - 1] + 1,
							  dist[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1)});
		}

	return dist[s1.length()][s2.length()];
}

template<typename T> int levenshtein(const vector<T> &v1, const vector<T> &v2) {
	if(v1.size() == 0) return v2.size();
	if(v2.size() == 0) return v1.size();

	vector<vector<int>> dist(v1.size() + 1, vector<int>(v2.size() + 1, (1 << 30) - 1));

	for(int i = 0; i <= v1.size(); i++) dist[i][0] = i;
	for(int i = 1; i <= v2.size(); i++) dist[0][i] = i;
	for(int i = 1; i <= v1.size(); i++)
		for(int j = 1; j <= v2.size(); j++) {
			dist[i][j] = min({dist[i - 1][j] + 1, dist[i][j - 1] + 1,
							  dist[i - 1][j - 1] + (v1[i - 1] == v2[j - 1] ? 0 : 1)});
		}

	return dist[v1.size()][v2.size()];
}

#line 2 "dp/levenshtein_distance.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

int levenshtein(const string &s1, const string &s2) {
	if(s1.length() == 0) return s2.length();
	if(s2.length() == 0) return s1.length();

	vector<vector<int>> dist(s1.length() + 1, vector<int>(s2.length() + 1, (1 << 30) - 1));

	for(int i = 0; i <= s1.length(); i++) dist[i][0] = i;
	for(int i = 1; i <= s2.length(); i++) dist[0][i] = i;
	for(int i = 1; i <= s1.length(); i++)
		for(int j = 1; j <= s2.length(); j++) {
			dist[i][j] = min({dist[i - 1][j] + 1, dist[i][j - 1] + 1,
							  dist[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1)});
		}

	return dist[s1.length()][s2.length()];
}

template<typename T> int levenshtein(const vector<T> &v1, const vector<T> &v2) {
	if(v1.size() == 0) return v2.size();
	if(v2.size() == 0) return v1.size();

	vector<vector<int>> dist(v1.size() + 1, vector<int>(v2.size() + 1, (1 << 30) - 1));

	for(int i = 0; i <= v1.size(); i++) dist[i][0] = i;
	for(int i = 1; i <= v2.size(); i++) dist[0][i] = i;
	for(int i = 1; i <= v1.size(); i++)
		for(int j = 1; j <= v2.size(); j++) {
			dist[i][j] = min({dist[i - 1][j] + 1, dist[i][j - 1] + 1,
							  dist[i - 1][j - 1] + (v1[i - 1] == v2[j - 1] ? 0 : 1)});
		}

	return dist[v1.size()][v2.size()];
}

Back to top page