如题，我在搜索 最小编辑距离 时看到到了一种神奇的数据结构 BK-Tree

说：

一次查询所遍历的节点不会超过所有节点的5%到8%，两次查询则一般不会17-25%，效率远远超过暴力枚举

然后我写了试试，但是 我的提交 它似乎比暴力还慢。

那么是我写的问题还是算法复杂度的问题？如果是我写法的问题，该怎么改？

参照 这篇 写出代码：

#include <vector>
#include <deque>
#include <algorithm>
#include <map>
#include <unordered_map>

#include <functional>

template<typename _t>
int levenshtein_distance(_t word1[], _t word2[], uint32_t len1 = 0, uint32_t len2 = 0)
{
	// https://en.wikipedia.org/wiki/Levenshtein_distance
	uint32_t i, j;

	if (!len1)while (word1[len1])len1++;
	if (!len2)while (word2[len2])len2++;

	std::vector<int> v0(len2 + 1), v1(len2 + 1);

	for (i = 0; i <= len2; ++i)v0[i] = i;

	for (i = 0; i < len1; ++i)
	{
		v1[0] = i + 1;

		for (j = 0; j < len2; ++j)
		{
			v1[j + 1] = std::min(
				{
				v0[j + 1] + 1,
				v1[j] + 1,
				v0[j] + (word1[i] != word2[j])
				}
			);
		}

		v0 = v1;
	}
	return v0[len2];
}

template<typename _t>
int levenshtein_distance(const _t& word1, const _t& word2)
{
	return levenshtein_distance(word1.data(), word2.data(), word1.size(), word2.size());
}

template<typename _t>
class dk_tree
{
public:

	using distance_func_t = std::function<int(const _t&, const _t&)>;

	distance_func_t dis_of = [](const _t& a, const _t& b) {
		return levenshtein_distance(a, b);
	};

	class node_t
	{
	public:
		node_t(const _t& val) :_val(val) {}
	private:

		//template<typename _t>
		friend class dk_tree;

		_t _val;
		std::map<int, uint32_t> _child;
	};

	uint32_t insert(const _t& val)
	{
		if (_data.empty())
		{
			_data.emplace_back(val);
			return 0;
		}
		return _insert_nocheck(val);
	}
	template<typename _iter_t>
	void insert(_iter_t first, _iter_t last)
	{
		if (_data.empty())
		{
			_data.emplace_back(*first);
			++first;
		}
		std::for_each(first, last, [this](const _t& x) {_insert_nocheck(x); });
	}
	void insert(std::initializer_list<_t> list)
	{
		insert(list.begin(), list.end());
	}

	void find(const _t& val, int radius, int& cnt)
	{
		std::deque<uint32_t> next_nodes;
		if (!_data.empty())next_nodes.push_back(0);

		int dis, L, R;

		while (!next_nodes.empty())
		{
			const auto& cur = _data[next_nodes.front()];
			next_nodes.pop_front();

			dis = dis_of(cur._val, val);

			if (dis <= radius)cnt++;

			R = dis + radius;

			for (L = std::max(0, dis - radius); L <= R; ++L)
			{
				const auto& it = cur._child.find(L);
				if (it != cur._child.end())
					next_nodes.push_back(it->second);
			}
		}
	}

private:

	std::vector<node_t> _data;

	uint32_t _insert_nocheck(const _t& val)
	{
		uint32_t cur_idx = 0;
		int dis;
		while (true)
		{
			dis = dis_of(val, _data[cur_idx]._val);
			if (!dis)return cur_idx;
			auto& idx = _data[cur_idx]._child[dis];
			if (!idx)
			{
				idx = _data.size();
				_data.emplace_back(val);
				return idx;
			}
			cur_idx = idx;
		}
		return -1; // not reached
	}
};

#include <iostream>
#include <stdio.h>

std::unordered_map<std::string,bool> mm;

int main()
{
	dk_tree<std::string> t;
	std::string s;

	int n, m;
	std::cin >> n >> m;
	while (n--)
	{
		std::cin >> s;
		t.insert(s);
		mm[s]=1;
	}

	std::vector<std::string> vec;
	int cnt;
	while (m--)
	{
		std::cin >> s;
		if(mm[s])
		{
		    puts("-1");
		    continue;
		}
		cnt=0;
		t.find(s, 1, cnt);
		std::cout<<cnt<<'\n';
	}

	return 0;
}