C++ প্রোগ্রাম: ওয়ান্গার এবং ফিশার অ্যালগরিদম দিয়ে অনলাইন স্ট্রিং ম্যাচিং

এই সেকশনে আমরা দেখব কীভাবে ওয়ান্গার এবং ফিশার অ্যালগরিদম ব্যবহার করে দুটি স্ট্রিং কম্পেয়ার করা যায়। এই অ্যালগরিদম ব্যবহার করে, আমরা বের করতে পারি সেই দুটি স্ট্রিং ম্যাচ করার জন্য কমপক্ষে কতগুলো পরিবর্তন দরকার।

এটি একটি ডাইনামিক প্রোগ্রামিং আপরোচ। এখানে আমরা দুটি স্ট্রিং থেকে লেভেনস্টাইন দূরত্ব মাপি।

ইনপুট: দুটি স্ট্রিং "Support" & "Suppose"
আউটপুট: মিনিমাম রিকোয়ার্ড চেঞ্জের সংখ্যা: 2

অ্যালগরিদম

Wagnwe_Fisher(str1, str2)

ইনপুট: দুটি স্ট্রিং str1 এবং str2
আউটপুট: মিনিমাম চেঞ্জের সংখ্যা

l1 := str1-এর দৈর্ঘ্য, এবং l2 = str2-এর দৈর্ঘ্য
d নামক ম্যাট্রিক্স ডিফাইন করুন অর্ডার (l1 * l2)
d-এর প্রথম সারি 0 থেকে l1-1 পর্যন্ত সংখ্যা দিয়ে ফিল করুন, এবং প্রথম কলাম 0 থেকে 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)
  লুপ শেষ
লুপ শেষ
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