सी ++ प्रोग्राम लेवेनशेटिन डिस्टेंस कंप्यूटिंग एल्गोरिथम को लागू करने के लिए

दो स्ट्रिंग्स के बीच लेवेनशेटिन दूरी का अर्थ है संपादन संचालन के साथ एक स्ट्रिंग को दूसरे में बदलने के लिए आवश्यक संपादनों की न्यूनतम संख्या; किसी एकल वर्ण का सम्मिलन, विलोपन या प्रतिस्थापन।

उदाहरण के लिए: लेवेनशेटिन बिल्ली और चटाई के बीच की दूरी 1 है -

cat mat(substitution of ‘c’ with ‘m’)

लेवेनशेटिन डिस्टेंस कंप्यूटिंग एल्गोरिथम को लागू करने के लिए यहां एक C++ प्रोग्राम दिया गया है।

एल्गोरिदम

Begin
   Take the strings as input and also find their length.
   For i = 0 to l1
      dist[0][i] = i
   For j = 0 to l2
      dist[j][0] = j
   For j=1 to l1
      For i=1 to l2
         if(s1[i-1] == s2[j-1])
            track= 0
         else
            track = 1
         done
         t = MIN((dist[i-1][j]+1),(dist[i][j-1]+1))
         dist[i][j] = MIN(t,(dist[i-1][j-1]+track))
      Done
   Done
   Print the Levinstein distance: dist[l2][l1]
End

उदाहरण

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
#define MIN(x,y) ((x) < (y) ? (x) : (y)) //calculate minimum between two values
int main() {
   int i,j,l1,l2,t,track;
   int dist[50][50];
   //take the strings as input
   char s1[] = "tutorials";
   char s2[] = "point";
   //stores the lenght of strings s1 and s2
   l1 = strlen(s1);
   l2= strlen(s2);
   for(i=0;i<=l1;i++) {
      dist[0][i] = i;
   }
   for(j=0;j<=l2;j++) {
      dist[j][0] = j;
   }
   for (j=1;j<=l1;j++) {
      for(i=1;i<=l2;i++) {
         if(s1[i-1] == s2[j-1]) {
            track= 0;
         } else {
            track = 1;
         }
         t = MIN((dist[i-1][j]+1),(dist[i][j-1]+1));
         dist[i][j] = MIN(t,(dist[i-1][j-1]+track));
      }
   }
   cout<<"The Levinstein distance is:"<<dist[l2][l1];
   return 0;
}

आउटपुट

The Levinstein distance is:8