#include <iostream> #include <string.h> using namespace std; int min(int x, int y, int z) { return (x<y)?(x<z?x:z):(y<z?y:z); } /* ed(s1[1,m], s2[1,n]) = ed(s1[1,m-1], s2[1,n-1]) if s1[m] == s2[n]; = 1+ min( ed(s1[1-m-1], s2[1,n]), remove s1[m] ed(s1[1-m-1], s2[1,n-1]) replace s1[m] with s2[n] ed(s1[1-m], s2[1,n-1]) ) insert s2[n] if s1[m] != s2[n] */ int editDistance(char* s1, int m, char* s2, int n) { if(m==0) return n; if(n==0) return m; if(s1[m-1] == s2[n-1]) { return editDistance(s1, m-1, s2, n-1); } return 1+ min(editDistance(s1,m-1, s2,n), \ editDistance(s1, m-1, s2, n-1), editDistance(s1, m, s2, n-1)); } int main() { // your code goes here char s1[] = "banana"; char s2[] = "bana"; char s3[] = "apple"; char s4[] = "banaba"; char s5[] = "bonanza"; char s6[] = "banamf"; cout << "edit of " << s1 << "-" << s2 << "=" \ << editDistance(s1,strlen(s1), s2, strlen(s2)) << endl; cout << "edit of " << s1 << "-" << s3 << "=" \ << editDistance(s1,strlen(s1), s3, strlen(s3)) << endl; cout << "edit of " << s1 << "-" << s4 << "=" \ << editDistance(s1,strlen(s1), s4, strlen(s4)) << endl; cout << "edit of " << s1 << "-" << s5 << "=" \ << editDistance(s1,strlen(s1), s5, strlen(s5)) << endl; cout << "edit of " << s1 << "-" << s6 << "=" \ << editDistance(s1,strlen(s1), s6, strlen(s6)) << endl; return 0; } edit of banana-bana=2 edit of banana-apple=5 edit of banana-banaba=1 edit of banana-bonanza=2 edit of banana-banamf=2
This blog site is dedicated for articles on problem solving using C, C++, data structures, algorithms. Besides this few technical articles are also presented.
Jun 25, 2017
edit distance of two strings
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment