---
title: "编辑距离"
created: 2025-11-28
tags:
  - 算法
---

# 编辑距离

## 题目 [编辑距离](https://www.acwing.com/problem/content/901/)

![[image-a9da0f9e.png]]

## 思路分析

和上题一样 这次是问有多少个能达到规定范围内

所以就是做多次最短编辑距离

![[image-477bcff3.png]]

![[image-23d415f1.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N = 1e1 + 5, M = 1e3 + 10, INF = 2e9;

int n, m;

char str[M][N];

int f[N][N];

int edit_distance(char a[], char b[])

{

    int la = strlen(a + 1), lb = strlen(b + 1);

    for(int i=1;i<=la;i++)

        for(int j=1;j<lb;j++)

            f[i][j]=INF;

    for(int i=0;i<=la;i++)

        f[i][0] = i;

    for(int i=0;i<=lb;i++)

        f[0][i] = i;

    for(int i=1;i<=la;i++)

    {

        for(int j=1;j<=lb;j++)

        {

            f[i][j]=min(f[i-1][j],f[i][j-1])+1;

            f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));

        }

    }

    return f[la][lb];

}

int main()

{

    cin>>n>>m;

    for(int i=0;i<n;i++)

        cin>>(str[i] + 1);

    while (m--)

    {

        int res = 0;

        char s[N];

        int limit;

        cin>>(s + 1)>>limit;

        for(int i=0;i<n;i++)

            if(edit_distance(str[i], s)<=limit)

                res++;

        cout<<res<<endl;

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[非递减子序列拓展思路|非递减子序列拓展思路]] 🏠 [[00-刷题理模型]] ➡️ [[线性dp|线性dp]]