最短编辑距离

给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：

1.删除–将字符串A中的某个字符删除。
2.插入–在字符串A的某个位置插入某个字符。
3.替换–将字符串A中的某个字符替换为另一个字符。
现在请你求出，将A变为B至少需要进行多少次操作。

输入格式
第一行包含整数n，表示字符串A的长度。

第二行包含一个长度为n的字符串A。

第三行包含整数m，表示字符串B的长度。

第四行包含一个长度为m的字符串B。

字符串中均只包含大写字母。

输出格式
输出一个整数，表示最少操作次数。

数据范围
1≤n,m≤1000

输入样例

10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例

4

代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;

typedef long long LL;
const int N = 1010;
char a[N], b[N];
int f[N][N];
int n, m;

int main()
{
    cin >> n >> a + 1>> m>> b + 1;//从1开始读入

    //初始化
    for (int i = 0; i <= n; i++)
        f[i][0] = i;
    for(int i = 0; i <= m;i++)
        f[0][i] = i;

    for(int i=1;i<=n;i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);//删除 插入
            if (a[i] == b[j])
                f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);//替换
        }

    printf("%d", f[n][m]);
    return 0;
}

编辑距离

给定n个长度不超过10的字符串以及m次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式
第一行包含两个整数n和m。

接下来n行，每行包含一个字符串，表示给定的字符串。

再接下来m行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过10。

输出格式
输出共m行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围
1≤n,m≤1000,

输入样例

3 2
abc
acd
bcd
ab 1
acbd 2

输出样例

1
3

代码

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;

typedef long long LL;
const int N = 1010;
char a[N], b[N];
char str[N][15];
int f[N][N];
int n, m;

int edit_distance(char a[],char b[])
{
    int lena = strlen(a+1);
    int lenb = strlen(b+1);

    //初始化
    for (int i = 0; i <= lena; i++)
        f[i][0] = i;
    for (int i = 0; i <= lenb; i++)
        f[0][i] = i;

    for (int i = 1; i <= lena; i++)
        for (int j = 1; j <= lenb; j++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);//删除 插入
            if (a[i] == b[j])
                f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);//替换
        }

    return f[lena][lenb];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        scanf("%s", str[i] + 1);//从1开始

    while (m--)
    {
        char s[15];
        int limit;
        int res = 0;
        scanf("%s%d", s + 1, &limit);

        for (int i = 0; i < n; i++)
        {
            if (edit_distance(str[i],s) <= limit)
                res++;
        }

        printf("%d\n", res);
    }

    return 0;
}