Program Overview

This program calculates the minimum edit distance (Levenshtein distance) between two strings using dynamic programming. The edit distance is defined as the minimum number of operations required to transform one string into the other, with the allowed operations being insertion, deletion, and substitution of a single character.

Program Structure

• Input: Two strings for which the minimum edit distance needs to be calculated.
• Dynamic Programming Table: A 2D array to store the distances between substrings of the two strings.
• Output: The minimum edit distance between the two strings.

C Program

#include 
#include 

// Function to calculate the minimum edit distance
int min(int a, int b, int c) {
    if (a < b && a < c) return a;
    if (b < c) return b;
    return c;
}

int editDistance(char *str1, char *str2, int m, int n) {
    int dp[m + 1][n + 1]; // DP table

    // Build the table in bottom-up manner
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            // If first string is empty
            if (i == 0) {
                dp[i][j] = j; // Min. operations = j (insert all characters of str2)
            }
            // If second string is empty
            else if (j == 0) {
                dp[i][j] = i; // Min. operations = i (remove all characters of str1)
            }
            // If last characters are the same
            else if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // No operation needed
            }
            // If last characters are different
            else {
                dp[i][j] = 1 + min(dp[i][j - 1],    // Insert
                                   dp[i - 1][j],    // Remove
                                   dp[i - 1][j - 1] // Replace
                                   );
            }
        }
    }

    return dp[m][n]; // Minimum edit distance is in dp[m][n]
}

// Main function
int main() {
    char str1[100], str2[100];

    // Input the two strings
    printf("Enter first string: ");
    scanf("%s", str1);
    printf("Enter second string: ");
    scanf("%s", str2);

    int m = strlen(str1);
    int n = strlen(str2);

    // Calculate the minimum edit distance
    int distance = editDistance(str1, str2, m, n);
    printf("Minimum Edit Distance: %d\n", distance);

    return 0;
}

Explanation of the Code

The program consists of two main parts: the function for calculating the minimum edit distance and the main function to handle input and output:

• The editDistance function implements the dynamic programming approach:
  • A 2D array dp is created to store the distances for substrings of str1 and str2.
  • The function iterates through each character of both strings, filling in the table based on whether the characters match or if an operation (insert, delete, substitute) is needed.
• The main function handles user input:
  • The user is prompted to enter two strings.
  • It calculates the minimum edit distance by calling the editDistance function and displays the result.

Usage

To use the program:

1. Compile the program using a C compiler (e.g., gcc).
2. Run the executable and input the two strings.
3. The program will output the minimum edit distance between the two strings.