$\Huge\color{orchid}{点击此处获取更多干货}$

莱文斯坦距离与动态规划

字符串的“编辑距离”是对两字符串差异程度的量化，量化的标准就是经过多少次处理能使一个字符串变得和另一个字符串完全相同。根据“处理”操作的不同，编辑距离有多种，此处支持单字符的插入，删除与修改的，就是莱文斯坦距离$\text{(Levenshtein Distance)}$，求解的方法就是动态规划。

和LCS一样，涉及了两个字符串$s,t$的话，$dp$表也得是二维的了。下面这张图表，展示了其中的状态表示和转移关系：

状态表示可以显而易见，接下来说一下三种操作下的转移关系。
1. 修改：我们尝试将$s[i]$修改成$t[j]$，只有当$s[i]\ne t[j]$时才会占用这一次处理的机会$(c=1)$，否则不占用$(c=0)$。然后在保证了最后一位相同的情况下，$s[1..i]$和$t[1..j]$之间的距离就可以从$s[1..i-1]$和$t[1..j-1]$之间的距离即$dp(i-1,j-1)$中得到，因此$dp(i,j)=dp(i-1,j-1)+c$
2. 增加：将$t[j]$对应的字符添加到$s$末尾，必然使用了1次处理机会，然后在$s[i+1]=t[j]$的情况下，$dp(i,j)$就可以从$s[1..i],t[1..j-1]$之间的距离$dp(i,j-1)$中得出，即$dp(i,j)=dp(i,j-1)+1$
3. 删除：如果说删除了$s[i]$后$s[i-1]=t[j]$，那么在$t$末尾添加$s[i]$的字符是一样的效果，都占用了1次处理机会，接下来就按照添加的方式去考虑，很容易就得出$dp(i,j)=dp(i-1,j)+1$
4. 以上三者的最小值就是莱文斯坦距离的值，因此真正的$dp(i,j)$应该等于$max\{dp(i-1,j-1)+c,dp(i,j-1)+1,dp(i-1,j)+1\}$

C++ 代码

下面的函数对应的是一对字符串，适配问题902.最短编辑距离

/**
 * @brief 字符串s与t之间的莱文斯坦编辑距离
 * @param s,t 待比较的两个字符串，默认让s变为t
 * @return 将s变为t所需最小处理次数
 * @note 为了方便计算，s和t已经事先在头部插入了一个无效字符，这样可以使有效部分的下标从1开始算
 * @warning s和t去掉头部的无效字符，都不能是空串，否则要抛出异常
 */
int levenDist(string& s, string& t) {
    if (s == " " || t == " ") {
        throw logic_error("不能和空串求编辑距离")
    }
    //虽然不支持空串，但是需要模拟从空串变为某一字符串的过程，记录处理次数
    for (int i = 0; i < t.size(); i++) {        //假设s为空，那么从s分别变成t[1..i]要经过i次处理
        dp[0][i] = i; 
    }
    for (int i = 0; i < s.size(); i++) {        //t为空时同理
        dp[i][0] = i;
    }
    for (int i = 1; i < s.size(); i++) {
        for (int j = 1; j < t.size(); j++) {    //递推
            int cost = (s[i] == t[j]) ? 0 : 1;
            dp[i][j] = min({ dp[i][j - 1] + 1, dp[i - 1][j] + 1, dp[i - 1][j - 1] + cost });
        }
    }
    return dp[s.size() - 1][t.size() - 1];      //dp(n,m)就是最终结果（需要把前置的无效字符去掉）
}

对于这次的问题，由于需求中已经限制了字符串的长度，因此在考虑了头部的占位字符之后，$dp$表可以直接构造为$11*11$。给出主函数：

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    string s;
    while (n--) {
        cin >> s;
        strs.push_back(" " + s);
    }
    while (m--) {
        int cnt = 0, limit;
        cin >> s >> limit;
        s = ' ' + s;
        for (auto& str : strs) {
            if (levenDist(s, str) <= limit) {
                cnt++;
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}