解题思路与方法

算法概述

本题要求在大量已知子命令中，根据用户输入的错误命令，找到与之最相似（即编辑距离最小）的子命令并提示。 最相似的定义为Levenshtein 距离，即将一个字符串通过 替换、插入、删除 三种基本操作变为另一个字符串所需的最少步数。

详细方法

1. 逐一计算编辑距离

题目内容

在使用命令行工具时，经常会出现手工输入错字母的情况，如想要输入:

git clone

输入成了

git clane

因此为了命令行工具更易用，需要从支持的子命令列表中找到最相似的子命令提示给用户。

最相似的定义为最短莱文斯坦距离:即两个字符串之间，由一个转成另一个所需的最少编辑操作次数。

允许的编辑操作包括:

1.将一个字符替换成另一个字符

2.插入一个字符

3.删除一个字符

输入描述

第一行给出可提示的最短距离$D$，第二行给出子命令数量$N$，后面N行给出所有的子命令 列表，最后一行给出用户输入的子命令。

$1<=D<=5$

$1<=N<=30000$

单个子命令长度$2<=L<=25$，子命令只包含小写字母

输出描述

输出为分三种情况:

1.用户输入的子命令正确匹配上某个子命令参数，输出原命令。

2.用户输入的子命令没有匹配上某个子命令参数，但是符合提示要求，则输出提示命令，如$clone$;如果符合提示要求的子命令有多个，则按距离从小到大排序后输出，同一个距离内还有多个的按字母序从小到大输出。

3.用户输入的子命令没有匹配上某个子命令参数，且没有符合提示要求的子命令，则输出$None$

样例1

输入

2
3
clone
checkout
switch
clane

输出

clone 

说明

第一行值为2，表示当前输入不能完全正确匹配某个子命令时，则将其最短距离小于2的子命令作为提示输出

第二行为3，表示命令行实际有3个子命令，分别为后续3行

最后一行为用户实际的输入

由于用户没有命中具体的子命令，而clone与用户输入的距离为1，满足小于2的要 求，因此输出clone

样例2

输入

2
3
clone
checkout
switch
create

输出

None

说明

输入的三个子命令中没有满足与$create$距离小于等于$2$的，因此输出$None$

样例3

输入

2
5
aprint
bprint
aaprint
bbprint
output
print

输出

aprint bprint aaprint bbprint

说明

子命令中有四个满足与$print$的距离小于等于$2$，其中$aprint$与$bprint$与目标的距离为$1$，先将其排序并输出，$aaprint\ bbprint$与目标的距离为$2$，排序后接在前面输出后继续输出