Longest Common Subsequence

Algorithm

1. If last charaters of \(a\) and \(b\) are same then repeat these steps again with \(a\) and \(b\) but both having one less size.

2. If last charaters are not same then take minimum of following three recursions

repeat with \(a\) and \(b\) but \(a\) has one less size.

repeat with \(a\) and \(b\) but \(b\) has one less size.

repeat with \(a\) and \(b\) but both have one less size.

Code :

    // edit distance

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int editd(string a, string b, int m, int n)
    {
        if (m == 0)
        {
            return n;
        }
        if (n == 0)
        {
            return m;
        }
        if (a[m - 1] == b[n - 1])
        {
            return editd(a, b, m - 1, n - 1);
        }
    
        return 1 + min(editd(a, b, m, n - 1), min(editd(a, b, m - 1, n), editd(a, b, m - 1, n - 1)));
    }
    
    int main()
    {
        string a, b;
        int m, n;
        cin >> a >> b;
        m = a.size();
        n = b.size();
        cout << "edit distance = " << editd(a, b, m, n) << "\n";
    }
                        
    

Complexity Analysis :

Time comeplexity : \( O(mn)\)