计算最小的编辑的距离的问题，怎么使用C语言的程序编写设计的代码技术的一个实现方式

Problem Description
There are two strings: A and B. We define an editing operation as “Insert a character”, “Delete a character” or “Replace a character”.
So your task is to calculate how many editing operations do we need to make B become the substring of A? If the answer is more than the given limitation, just output -1.

Input
Multiple test cases.
There are 3 lines in each test case:
String A is given in the first line, and the length of A is from 0 to 1000000.
String B is given in the second line, and the length of B is from 0 to 1000.
In the third line, there is an integer LIM. （0<= LIM <=30）

Output
Print the number of editing operations in one line. If the answer is more than LIM, just output -1.

Sample Input
annealing
annual
3

Sample Output
1

#include <stdio.h>
#include <string.h>
#include <malloc.h>

int ed[100][100];

int min(int a,int b,int c)
{
   if(a>b) a=b;
   if(a>c) a=c;
   return a;
}

void edit_dist1(char *A,char *B)
{
   if(A[0]==B[0]) ed[0][0]=0;
   else ed[0][0]=1;
   int i;
   int x;
   for(i=1;i<strlen(B);i++)
   {   
       x=ed[0][i-1]+1-(int)(A[0]==B[i]);
       ed[0][i]=i>x?i:x;
   }
   for(i=1;i<strlen(A);i++)
   {
       x=ed[i-1][0]+1-(int)(A[i]==B[0]);
       ed[i][0]=i>x?i:x;
   }
}

void edit_dist2(char* A,char* B)
{
   int i,j;
   for(i=1;i<strlen(A);i++)
       for(j=1;j<strlen(B);j++)
       {
          if(A[i]==B[j])
              ed[i][j]=ed[i-1][j-1];
          else
              ed[i][j]=min(ed[i-1][j-1],ed[i-1][j],ed[i][j-1])+1;
       }
}

int main()
{
   while(true)
   {
       char *A;
       A=(char*)malloc(100*sizeof(char));
       scanf("%s",A);
       char *B;
       B=(char*)malloc(100*sizeof(char));
       scanf("%s",B);
       edit_dist1(A,B);
       edit_dist2(A,B);

       for(int i=0;i<strlen(A);i++)
       {
         for(int j=0;j<strlen(B);j++)
             printf("%d",ed[i][j]);
         printf("\n");
       }
       printf("编辑距离为%d\n",ed[strlen(A)-1][strlen(B)-1]);
       free(A);
       free(B);
   }
   return 0;
}

作者：浪漫代码
来源：CSDN
原文：https://blog.csdn.net/u010797915/article/details/9884191
版权声明：本文为博主原创文章，转载请附上博文链接！