Created
January 14, 2017 04:12
-
-
Save jonpchin/f277f0956b7002fe10b3c65886cbcd61 to your computer and use it in GitHub Desktop.
Algorithm to quantify how similar two strings are
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Jonthan Chin | |
| // 11/15/15 | |
| // Minnimum Edit Distance algorithm which finds the minnimum | |
| //number of character insertions, deletions, or replacements to make one string equal to another string | |
| #include <stdio.h> | |
| #include <string.h> | |
| #define MIN(a,b)( ((a) > (b)) ? (b) : (a)) | |
| int main() | |
| { | |
| FILE *ifp = fopen("input.txt", "r"); | |
| char word1[100]; | |
| char word2[100]; | |
| fgets(word1, 99, ifp); | |
| fgets(word2, 99, ifp); | |
| fclose(ifp); | |
| int lengthA = strlen(word1); | |
| int lengthB = strlen(word2); | |
| char storage[lengthA+1][lengthB+1]; | |
| int i; | |
| for(i=0; i<lengthB+1; i++){ | |
| storage[0][i]=i; | |
| } | |
| for(i=0; i<lengthA+1; i++){ | |
| storage[i][0]=i; | |
| } | |
| int j; | |
| for(i=0; i<lengthA; i++){ | |
| for(j=0; j<lengthB; j++){ | |
| if(word1[i]==word2[j]){ | |
| //then the value diagonal of it is equal | |
| storage[i+1][j+1] = storage[i][j]; | |
| } | |
| //otherwise its the minnimum of the three values, diagonal, left and upper plus 1 | |
| else{ | |
| int value = MIN(storage[i][j+1], storage[i+1][j]); | |
| storage[i+1][j+1] = MIN(storage[i][j], value)+1; | |
| } | |
| } | |
| } | |
| int total = storage[lengthA][lengthB]; | |
| printf("Minnimum edit distance is %d\n", total); | |
| return 0; | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| jonbenjaminisverycool | |
| sadfsdjonasdfdsfissdfasdfwerwercool |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment