โปรแกรม C++ เพื่อใช้ Wagner และ Fisher Algorithm สำหรับการจับคู่สตริงออนไลน์

ในส่วนนี้ เราจะมาดูวิธีเปรียบเทียบสองสตริงโดยใช้อัลกอริธึม Wagner และ Fisher เมื่อใช้อัลกอริทึมนี้ เราสามารถค้นหาจำนวนการเปลี่ยนแปลงขั้นต่ำที่จำเป็นเพื่อให้ตรงกับสตริงเหล่านั้น

นี่เป็นแนวทางการเขียนโปรแกรมแบบไดนามิก ที่นี่เราวัดระยะทาง Levenshtein จากสองสาย

Input: Two strings “Support” & “Suppose”
Output: Minimum number of required changes: 2

อัลกอริทึม

Wagnwe_Fisher(str1, str2)

ป้อนข้อมูล :สองสาย str1 และ str2
ผลผลิต :จำนวนการเปลี่ยนแปลงขั้นต่ำ

l1 := length of str1, and l2 = length of str2
define a matrix d of order (l1 * l2)
fill first row of d with numbers from 0 to l1 – 1, and fill first column with numbers from 0 to l2- 1
for j in range 1 to l1, do
   for i in range 1 to l2, do
      if str1[i - 1] = str2[j - 1], then
         tracker := 1
      else
         tracker := 0
      temp := minimum of d[i – 1, j] + 1 and d[i, j-1] + 1
      d[i, j] = minimum of temp and (d[i – 1, j - 1]+ tracker)
   done
done
return d[l2, l1]

โค้ดตัวอย่าง

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int d[100][100];
int min(int a, int b) {
   return (a < b) ? a : b;
}
int main() {
   int i,j,str1_len,str2_len,temp,tracker; 
   string str1 = "Support";
   string str2 = "Suppose";
   str1_len = str1.length();
   str2_len = str2.length();
   for(i = 0; i <= str1_len;i++)
      d[0][i] = i;
   for(j = 0;j <= str2_len;j++)
      d[j][0] = j;
   for (j = 1;j <= str1_len; j++) {
      for(i = 1;i <= str2_len;i++) {
         if(str1[i-1] == str2[j-1]) {
            tracker = 0;
         } else {
            tracker = 1;
         }
         temp = min((d[i-1][j]+1),(d[i][j-1]+1));
         d[i][j] = min(temp,(d[i-1][j-1]+tracker));
      }
   }
   cout << "The Levinstein distance " << d[str2_len][str1_len];
}

ผลลัพธ์:

The Levinstein distance 2