/* editdistance.h Header file for string comparison */ /* Copyright 2003-2020 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. These programs appear in my books: "The Algorithm Design Manual" by Steven Skiena, second edition, Springer, London 2008. See out website www.algorist.com for additional information or https://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorith01-20 "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information, or https://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #define MAXLEN 101 /* longest possible string */ /* [[[ editdistance_mid_cut */ #define MATCH 0 /* enumerated type symbol for match */ #define INSERT 1 /* enumerated type symbol for insert */ #define DELETE 2 /* enumerated type symbol for delete */ /* ]]] */ /* [[[ editdistance_cell_struct_cut */ typedef struct { int cost; /* cost of reaching this cell */ int parent; /* parent cell */ } cell; /* ]]] */ void row_init(int i, cell m[MAXLEN+1][MAXLEN+1]); void column_init(int i, cell m[MAXLEN+1][MAXLEN+1]); int match(char c, char d); int indel(char c); void goal_cell(char *s, char *t, int *i, int *j); void delete_out(char *s, int i); void insert_out(char *t, int j); void match_out(char *s, char *t, int i, int j); int string_compare(char *s, char *t, cell m[MAXLEN+1][MAXLEN+1]); int string_compare_r(char *s, char *t, int i, int j); void reconstruct_path(char *s, char *t, int i, int j, cell m[MAXLEN+1][MAXLEN+1]); void print_matrix(char *s, char *t, bool costQ, cell m[MAXLEN+1][MAXLEN+1]);