3
\$\begingroup\$

I am to convert a given string into another using only three basic operations, that is by deleting, inserting or replacing a character. Changes can only be made to string 1 and it is given that the sum of the lengths of the two strings does not exceed 25.

I have tried a recursive statement that cycles through all possibilities. It immediately returns if either the number of steps is greater than or equal to the already found minimum amount of steps or if the 'error' is greater than or equal to the error before the last operation.

The error is defined as the number of non-matching characters in the first n =min{len1,len2} characters, where len1 and len2 correspond to the lengths of strings 1 and 2, respectively, plus the absolute difference between lengths.

Looping through possibilities for inserting and replacing characters is restricted to the unique elements of the second string.

The resulting program works, but it not nearly fast enough, so I need to narrow down the searching process. I have tried adding the constraint that a newly added or a replaced character should increase length of the longest matching string that can be found in both sequences by merely deleting elements (e.g in abcef and bzxycf this would be bcf), but to no avail.

Any suggestions on improvements? The function of interest is minOps().

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void readWords(char *word1, int* len1, char *word2, int* len2) {
    char c = getchar();
    *len1 = 0;
    *len2 = 0;

    while (c!='\n') {
        word1[*len1] = c;
        *len1 = *len1+1;
        c = getchar();
    }

    c = getchar();
    while (c!='\n') {
        word2[*len2] = c;
        *len2 = *len2+1;
        c = getchar();
    }

    return;
}

char *insert(char* word, int len, char c, int loc) {
    char* copy = calloc(len+1, sizeof(char));
    for (int i=0; (i<len); i++) {
        if (i==loc) {copy[i] = c;}
        copy[i+(i>=loc)] = word[i];
    }
    if (loc==len) {copy[len] = c;}
    return copy;
}

char *delete(char* word, int len, int loc) {
    char* copy = calloc(len-1, sizeof(char));
    for (int i=0; (i<len); i++) {
        if (i!=loc) {copy[i-(i>=loc)] = word[i];}
    }
    return copy;
}

char *uniqueChars(char *word, int len, int *numOfUniqs) {
    char *uniques = calloc(len, sizeof(char));
    int k=0, notUnique;

    for (int i=0; (i<len); i++) {
        notUnique = 0;
        for (int j=0; (j<k); j++) {
            if (word[i]==uniques[j]) {notUnique = 1;}
        }
        if (notUnique == 0) {uniques[k] = word[i]; k++;}
    }

    /* no realloc at every step of the for loop */
    char* copy = calloc(k, sizeof(char));
    for (int i=0; (i<k); i++) {copy[i]=uniques[i];}
    free(uniques);

    *numOfUniqs = k;
    return copy;
}

/* error measurement */
int misMatch(char *word1, int len1, char *word2, int len2) {
    int err = abs(len1-len2), minLen;
    if (len1<len2) {minLen = len1;} else {minLen = len2;}
    for (int i=0; (i<minLen); i++) {err += (word1[i]!=word2[i]);}
    return err;
}

/* maxMatch: find length of the longest matching substring that can be 
 *                   found in both strings by only deleting elements */
int maxMatch(char *word1, int len1, char *word2, int len2)  {
    int k, max=0, candidate, prev;
    for (int j=0; (j<len1); j++) {
        candidate = 0; prev=-1;
            for (int i=j; (i<len1); i++) {
                k = 1; 
                while ((word1[i]!=word2[prev+k]) && (prev+k<len2)) {k++;}
                if (prev+k<len2) {candidate++; prev += k;}
            }
            if (max < candidate) {max = candidate;}
        }

    for (int j=0; (j<len2); j++) {
        candidate = 0; prev=-1;
            for (int i=j; (i<len2); i++) {
                k = 1; 
                while ((word2[i]!=word1[prev+k]) && (prev+k<len1)) {k++;}
                if (prev+k<len1) {candidate++; prev += k;}
            }
            if (max < candidate) {max = candidate;}
        }

    return max;
}


int minOps(char *word1, int len1, char *word2, int len2, int minSteps,
                     char* uniques, int numOfUniqs, int prevErr, int steps) {            
    /* return if number of steps equals minSteps; for then the sequence
     * of operations is no improvement to the current optimum */
    if (minSteps <= steps) {return 25;}         

    /* determine whether the current string is an improvement wrt the
     * previous */
    int err = misMatch(word1, len1, word2, len2);
    if (prevErr <= err) {return 25;}

    /* find longest matching segment */
    int max = maxMatch(word1, len1, word2, len2);

    /* BASE CASE -- words match, i.e. err = 0 ------------------------ */
    if (err == 0) {return steps;}

    /* RECURSIVE CASE ------------------------------------------------ */
    char* copy;
    int current;

    /* check deletions */
    if (len1 > len2) {
        for (int i=0; (i<len1); i++) {
            copy = delete(word1, len1, i);
            if (maxMatch(word1, len1, word2, len2) >= max) {
                current = minOps(copy, len1-1, word2, len2, minSteps,
                                                 uniques,   numOfUniqs, err, steps+1);
                if (current < minSteps) {minSteps = current;}
            }
            free(copy);
        }
    }

    /* check insertions */
    if (len1 < len2) {
        for (int i=0; (i<len1+1); i++) {
            for (int j=0; (j<numOfUniqs); j++) {
                copy = insert(word1, len1, uniques[j], i);

                if (maxMatch(copy, len1+1, word2, len2) >= max) {
                    current = minOps(copy, len1+1, word2, len2, minSteps,
                                                     uniques,   numOfUniqs, err, steps+1);
                    if (current < minSteps) {minSteps = current;}
                }
                free(copy);
            }
        }
    }

    /* check replacements */
    char mem;
    for (int i=0; (i<len1); i++) {
        for (int j=0; (j<numOfUniqs); j++) {
            if (word1[i]!=uniques[j]) {
                mem = word1[i];
                word1[i] = uniques[j]; 

                if (maxMatch(word1, len1, word2, len2) >= max) {
                    current = minOps(word1, len1, word2, len2, minSteps,
                                                     uniques,   numOfUniqs, err, steps+1);
                    if (current < minSteps) {minSteps = current;}
                }
                word1[i] = mem;
            }
        }
    }

    return minSteps;
}

int main() {
    /* read words */
    char* word1 = calloc(25, sizeof(char));
    char* word2 = calloc(25, sizeof(char));
    int len1, len2, *len1ptr = &len1, *len2ptr = &len2;
    readWords(word1, len1ptr, word2, len2ptr);

    /* determine maximum amount of operations needed (=min{len1,len2}) */
    int maxOp;
    if (len1>len2) {maxOp = len1;} else {maxOp = len2;}

    /* determine the unique characters of the second string */
    int numOfUniqs, *numOfUniqsPtr = &numOfUniqs;
    char* uniques = uniqueChars(word2, len2, numOfUniqsPtr);

    /*printf("%d\n", maxMatch(word1, len1, word2, len2));*/


    printf("%d", minOps(word1, len1, word2, len2, maxOp, uniques,
                                            numOfUniqs, 25, 0)); 
    return 0;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ The algorithm you describe is called the Levenshtein distance. Maybe this helps you to find more information. \$\endgroup\$ – Roland Illig Oct 24 '17 at 6:16
  • 1
    \$\begingroup\$ Also called edit-distance - I've added the tag for you. \$\endgroup\$ – Toby Speight Oct 24 '17 at 9:21
  • \$\begingroup\$ @RolandIllig and TobySpeight spot-on, thanks a lot! \$\endgroup\$ – User2935032946 Oct 24 '17 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.