Count common sub-sequences in two strings in C++

Understanding Common Subsequences

A common subsequence of two strings is a sequence that appears in both strings in the same relative order but not necessarily contiguously.

We will explore three different methods to count common sub-sequences in two strings using C++.

Method 1: Using Recursion

This method recursively finds the count of common sub-sequences.

#include <iostream>
#include <algorithm>
using namespace std;

int countSubsequences(string str1, string str2, int m, int n) {
    if (m == 0 || n == 0)
        return 0;
    if (str1[m - 1] == str2[n - 1])
        return 1 + countSubsequences(str1, str2, m - 1, n - 1);
    else
        return countSubsequences(str1, str2, m - 1, n) + countSubsequences(str1, str2, m, n - 1);
}

int main() {
    string str1 = "abc";
    string str2 = "ac";
    cout << "Common Subsequences Count: " << countSubsequences(str1, str2, str1.length(), str2.length()) << endl;
    return 0;
}
            

Method 2: Using Dynamic Programming

This method uses a DP table to count common sub-sequences efficiently.

#include <iostream>
#include <algorithm>
using namespace std;

int dpSubsequences(string str1, string str2) {
    int m = str1.length(), n = str2.length();
    int dp[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (str1[i - 1] == str2[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m][n];
}

int main() {
    string str1 = "abc";
    string str2 = "ac";
    cout << "Common Subsequences Count: " << dpSubsequences(str1, str2) << endl;
    return 0;
}
            

Method 3: Using Bitmasking

This method uses bitwise operations to find the count of common sub-sequences.

#include <iostream>
#include <algorithm>
using namespace std;

int countWithBitmask(string str1, string str2) {
    int count = 0;
    int len1 = str1.length(), len2 = str2.length();
    for (int i = 0; i < (1 << len1); i++) {
        string sub1 = "";
        for (int j = 0; j < len1; j++) {
            if (i & (1 << j)) sub1 += str1[j];
        }
        if (str2.find(sub1) != string::npos)
            count++;
    }
    return count;
}

int main() {
    string str1 = "abc";
    string str2 = "ac";
    cout << "Common Subsequences Count: " << countWithBitmask(str1, str2) << endl;
    return 0;
}