很早以前写过一题非常类似的，不过这次在这基础上增改了一些，也算“实用”的OI题了吧233333

（注：键盘距离：每个键键宽、高定义为1，两排按键之间垂直间隔1，跨排相邻键的水平间隔为0.5，如下图。字母错序的键盘距离规定为1）

主要添加的有意思的地方还是编辑距离中的键盘距离。原本题不是特别难，所以增加了一些订正可能和键盘距离这样的设定。（然而还是不难）

dalao说用字典树写……不是很懂dalao啊。我的打算是：先生成任何可能的词，通过布隆过滤器来选出存在单词，再计算距离排序。因为题目中对错误字母有上界2，所以枚举全部可能也不是很复杂。但实际情况却不是特别乐观。比如对词：congratulation，订正两个字母有$latex C_{14}^{2}\cdot (26-1)=2275$种，增加$latex \frac{(15+2-1)!}{((15-1)!\cdot 2!)}\cdot 26=3120$种，删去$latex C_{14}^{2}=91$种，换序$latex C_{14}^{2}+C_{12}^{2}=157$种，总共5643种。讲道理，布隆过滤器虽然很快，但也没那么快啊……仔细观察，发现订正和增加的可能特别多，因为需要考虑到26个字母（或25个）。那为何不取当前字母附近的字母先判断呢？如果不够再继续取（一般不会）。最近的一圈最大是7个字母，订正瞬间变成637，增加变成340。比原来少了将近80%。而且事实上键盘里靠近键为7的键只有5个而已（字母），不考虑字母出现频率，平均每个键附近大概是4.7个键左右。这样算起来，能把数量降到1200。而布隆过滤器可是算的飞快啊。至于怎么搞邻近键……kd树之。另外值得一提的是，可以把生成拆分开来，以便于编辑距离的快速计算。

期待dalao的实现……