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 <stdio.h>
#include <string.h>

int countSubsequences(char *str1, char *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() {
    char str1[] = "abc";
    char str2[] = "ac";
    printf("Common Subsequences Count: %d\n", countSubsequences(str1, str2, strlen(str1), strlen(str2)));
    return 0;
}
            

Method 2: Using Dynamic Programming

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

#include <stdio.h>
#include <string.h>

int dpSubsequences(char *str1, char *str2) {
    int m = strlen(str1), n = strlen(str2);
    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() {
    char str1[] = "abc";
    char str2[] = "ac";
    printf("Common Subsequences Count: %d\n", dpSubsequences(str1, str2));
    return 0;
}
            

Method 3: Using Bitmasking

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

#include <stdio.h>
#include <string.h>

int countWithBitmask(char *str1, char *str2) {
    int count = 0;
    int len1 = strlen(str1), len2 = strlen(str2);
    for (int i = 0; i < (1 << len1); i++) {
        char sub1[100] = "", sub2[100] = "";
        int idx = 0;
        for (int j = 0; j < len1; j++) {
            if (i & (1 << j)) sub1[idx++] = str1[j];
        }
        sub1[idx] = '\0';
        if (strstr(str2, sub1) != NULL)
            count++;
    }
    return count;
}

int main() {
    char str1[] = "abc";
    char str2[] = "ac";
    printf("Common Subsequences Count: %d\n", countWithBitmask(str1, str2));
    return 0;
}