01: #include<stdio.h>
02: #include<stdlib.h>
03: #include<string.h> // per funzioni di stringa
04: #include<ctype.h>  // per conversione minuscolo/maiuscolo
05: 
06: char *leggistringa(void);
07: int leve(char *, char *);
08: int min(int, int, int);
09: 
10: int main(int argc, char **argv){
11: 
12:   // li definisco per gestire i due array che conterranno le stringhe
13:   char *s1, *s2;
14: 
15:   // mi avvalgo di funzioni per leggere le stringhe
16:   printf("Inserisci la prima   stringa: ");
17:   s1 = leggistringa();
18:   printf("Inserisci la seconda stringa: ");
19:   s2 = leggistringa();
20: 
21:   // calcolo la loro "somiglianza"
22:   int dl = leve(s1, s2);
23: 
24:   printf("Il numero di caratteri da modificare, cancellare o inserire per trasformare [%s] in [%s] e' pari a %d\n", s1, s2, dl);
25: 
26:   // s1 e s2 non servono piu', disalloco
27:   free(s1);
28:   free(s2);
29: 
30:   return 0;
31: }
32: 
33: // funzione che calcola e restituisce un parametro "somiglianza" delle due stringhe
34: // in input, calcolato in base all'algoritmo riportato sul testo
35: int leve(char *s1, char *s2)
36: {
37:   // calcolo lunghezze stringhe
38:   int l1 = strlen(s1);
39:   int l2 = strlen(s2);
40: 
41:   // alloco matrice (VLA qui va bene, visto che e' tutto interno alla funzione, pone dei limiti di dimensioni ma per il caso d'uso e' ragionevole)
42:   int mat[l2+1][l1+1];
43:   
44:   // inizializzo prima riga e prima colonna
45:   for(int i = 0; i <= l1; ++i)
46:     mat[0][i] = i;  // rammento che la prima coordinata e' l'indice di riga
47: 
48:   for(int i = 0; i <= l2; ++i)
49:     mat[i][0] = i;
50: 
51:   // confronto a coppie i caratteri delle due stringhe partendo da sinistra
52:   // verso destra
53:   int costo;
54:   for(int i = 0; i < l1; ++i)
55:     for(int j = 0; j < l2; ++j)
56:     {
57:       // sono diversi i due caratteri?
58:       if(tolower(s1[i]) == tolower(s2[j])) // confronto le lettere minuscole per il punto #4 (non funzionerebbe con lettere accentate che, come detto a lezione, evitiamo di usare)
59:                                      // nel caso andrebbe usato tolower((unsigned char)s1[i]) == ...
60:   costo = 0;
61:       else
62:   costo = 1;
63:       mat[j+1][i+1] = min(mat[j+1][i] + 1, mat[j][i+1] + 1, mat[j][i] + costo);  // mi avvalgo di funzione per calcolare il minimo tra 3 valori
64:     }
65: 
66:   return mat[l2][l1];
67: }
68: 
69: // funzione che legge una stringa e restituisce array allocato dinamicamente che la contiene
70: char *leggistringa(void)
71: {
72:   char tmp[1000];                      // buffer di appoggio "sufficientemente" largo
73:   scanf(" %s", tmp);                   // leggo 
74: 
75:   char *x = malloc(strlen(tmp) + 1);   // alloco array di dimensioni adeguate alla stringa da contenere
76:   strcpy(x, tmp);                      // ce la copio dentro
77: 
78:   return x;                            // e la restituisco (chi chiama la funzione dovra' poi gestire la disallocazione
79: }
80: 
81: // restituisce minimo tra tre valori
82: int min(int a, int b, int c)
83: {
84:   if(a <= b && a <= c)
85:     return a;
86:   if(b <= c)
87:     return b;
88:   return c;
89: }
90: 
91: