c++ - Edit distance recursive algorithm -- Skiena -


i'm reading algorithm design manual steven skiena, , i'm on dynamic programming chapter. has example code edit distance , uses functions explained neither in book nor on internet. i'm wondering

a) how algorithm work?

b) functions indel , match do?

#define match     0       /* enumerated type symbol match */ #define insert    1       /* enumerated type symbol insert */ #define delete    2       /* enumerated type symbol delete */  int string_compare(char *s, char *t, int i, int j) {         int k;                  /* counter */         int opt[3];             /* cost of 3 options */         int lowest_cost;        /* lowest cost */          if (i == 0) return(j * indel(' '));         if (j == 0) return(i * indel(' '));          opt[match] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);         opt[insert] = string_compare(s,t,i,j-1) + indel(t[j]);         opt[delete] = string_compare(s,t,i-1,j) + indel(s[i]);          lowest_cost = opt[match];         (k=insert; k<=delete; k++)                 if (opt[k] < lowest_cost) lowest_cost = opt[k];          return( lowest_cost ); }

on page 287 in book:

int match(char c, char d) {   if (c == d) return(0);    else return(1);  }  int indel(char c) {   return(1); }

Comments

Post a Comment

Popular posts from this blog

java.util.scanner - How to read and add only numbers to array from a text file -

i'm learning java , have question regarding reading file want read numbers file contains strings well. here example of file: 66.56 "3 java 3-43 5-42 2.1 1 and here coding: public class test { public static void main (string [] args){ if (0 < args.length) { file x = new file(args[0]); try{ scanner in = new scanner( new fileinputstream(x)); arraylist<double> test = new arraylist<>(); while(in.hasnext()){ if(in.hasnextdouble()){ double f=in.nextdouble(); test.add(f);} else {in.next();} } catch(ioexception e) { system.err.println("exception during reading: " + e); } } my problem add 66.56,2.1 , 1 doesn't add 3 after "3 or ignores 3-43 , 5-42 can tell me how skip strings , add doubles here? thanks all said 3 ie; "3, 3-43 , 4-42 strings either u read string , split , check number @ " , - or put in space between characters , integers. jvm after compilation tre...
Read more

rewrite - Trouble with Wordpress multiple custom querystrings -

i'm working on adding multiple querystring , doesn't seem work. i've found codes seems work others might i'm missing something. i want like: http://mydomain.com/board/?getyear=2013&getsometext2=sometext to http://mydomain.com/board/2013/sometext/ i added code below functions.php file. doesn't seem work should though. this works. echoing querystring gets both variable without problem. http://mydomain.com/board/2013/sometext/ but doesn't. tested querystring vis isset() seems nothing being set/get http://mydomain.com/board/2013/ function add_query_vars($vars) { $vars[] = "getyear"; $vars[] = "getsometext2"; return $vars; } add_filter('query_vars', 'add_query_vars'); function add_rewrite_rules($arules) { $anewrules = array('board/([^/]+)/([^/]+)/?$' => 'index.php?pagename=board&getyear=$matches[1]&getsometext2=$matches[2]'); $arules = $a...
Read more