Facebook
From Sweet Cheetah, 1 Week ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 73
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. int d[101][101], n, m;
  5. char s1[101][82], s2[101][82];
  6.  
  7. void citire(int &n, char s[][82]){
  8.     scanf("%d", &n);
  9.     for(int i = 1; i <= n; i++)
  10.         scanf("%s", s[i]);
  11. }
  12.  
  13. void solve(){
  14.     d[0][0] = 0;
  15.     for(int i = 1; i <= m; i++)
  16.         d[i][0] = i;
  17.     for(int j = 1; j <= n; j++)
  18.         d[0][j] = j;
  19.     for(int i = 1; i <= m; i++){
  20.         for(int j = 1; j <= n; j++)
  21.            
  22.             if(strcmp(s1[i], s2[j]) != 0){
  23.                 int x = d[i-1][j-1] + 1;
  24.                 if(x > d[i][j-1] + 1)
  25.                     x = d[i][j-1] + 1;
  26.                 if(x > d[i-1][j] + 1)
  27.                     x = d[i-1][j] +1;
  28.                 d[i][j] = x;
  29.             }
  30.             else d[i][j] = d[i-1][j-1];
  31.     }
  32.    
  33. }
  34.  
  35. int main(){
  36.     citire(n,s1);
  37.     citire(m,s2);
  38.     m++;n++;
  39.     solve();
  40.     d[m-1][n-1]-=1;
  41.     for(int i = 0; i < m; i++){
  42.         for(int j = 0; j < n; j++)
  43.             printf("%d ", d[i][j]);
  44.         printf("\n");
  45.     }
  46.     printf("%d", d[m-1][n-1]);
  47.     return 0;
  48. }