解题思路与方法

算法概述

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

详细方法

1. 逐一计算编辑距离

题目内容

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

git clone

输入成了

git clane

因此为了命令行工具更易用，需要从支持的子命令列表中找到最相似的子命令提示给用户。最相似的定义为最短莱文斯坦距离：即两个字符串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括：

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

$2.$插入一个字符

$3.$删除一个字符

输入描述

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

约束：

• $1≤D≤5$
• $1≤N≤30000$
• 单个子命令长度 ，子命令只包含小写字母

输出描述

输出为分三种情况：

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

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

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

样例1

输入

2
5
aprint
bprint
aaprint
bbprint
output
print

输出

aprint bprint aaprint bbprint

说明

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

样例2

输入

2
3
clone
checkout
switch
create

输出

None

说明

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

样例3

输入

2
3
clone
checkout
switch
clane

输出

clone

说明

第一行值为$2$，表示当前输入不能完全正确匹配某个子命令时，则将其最短距离小于$2$的子命令作为提示输出；第二行为$3$，表示命令行实际有$3$个子命令，分别为后续$3$行；最后一行为用户实际的输入。由于用户没有命中具体的子命令，而 $clone$与用户输入的距离为$1$，满足小于$2$的要求，因此输出 $clone$