Program to count the common sub sequence of two strings is discussed here. Given two strings, count all the common sub-sequences of the two strings and print it.

For example,**Input:**

string 1 = “abcd”

string 2 = “abc”**Output:**

Number of common sub-sequences = 7**Common sub-sequences:** ‘a’, ‘b’, ‘c’, ‘ab’, ‘bc’, ‘ac’, ‘abc’.

**Input:**

String 1 : bajdpmk

String 2 : dimnkc**Output:**

Number of common sub-sequences = 7**Common sub-sequences:** ‘d’, ‘k’, ‘m’, ‘dk’, ‘km’, ‘dm’, ‘dmk’.

**Algorithm to count the common sub sequence of two strings**

- Input both the strings.
- Define arr[i][j] = arr[i][j-1] + arr[i-1][j] + 1, when s1[i-1] is equal to s2[j-1]
- When s1[i-1] == s1[j-1], all previous common sub-sequences are doubles as they ger appended by one another character.
- Both arr[i][j-1] and arr[i-1][j] contain arr[i-1][j-1] and hence it gets added two times in recurrence which takes care of doubling the count of all previous common sub-sequences.
- Addition of 1 in recurrence is done for the latest character match, which is the common sub-sequence made up of s1[i-1] and s2[j-1] = arr[i-1][j] + arr[i][j-1] – arr[i-1][j-1], when s1[i-1] is not equal to s2[j-1].
- Subtract arr[i-1][j-1] once because it is present in both arr[i][j – 1] and arr[i – 1][j] and is added twice.

Program to count the common sub sequence of two strings is discussed here.

/* C program to count the common sub sequence of two strings */

#include <stdio.h>

#include <string.h>

// Function to find common sub sequence in both strings

int count_common_sub_sequence(char s1[], char s2[])

{

int n1, n2;

n1 = strlen(s1);

n2 = strlen(s2);

int arr[n1+1][n2+1];

for (int i = 0; i <= n1; i++)

{

for (int j = 0; j <= n2; j++)

{

arr[i][j] = 0;

}

}

// for each character of S1

for (int i = 1; i <= n1; i++)

{

// for each character in S2

for (int j = 1; j <= n2; j++)

{

// if character are same in both the string

if (s1[i – 1] == s2[j – 1])

{

arr[i][j] = 1 + arr[i][j – 1] + arr[i – 1][j];

}

else

{

arr[i][j] = arr[i][j – 1] + arr[i – 1][j] – arr[i – 1][j – 1];

}

}

}

return arr[n1][n2];

}

int main()

{

char s1[10];

char s2[10];

printf(“\nEnter string 1 : “);

gets(s1);

printf(“\nEnter string 2 : “);

gets(s2);

printf(“\nCount of common sub sequence is %d\n”, count_common_sub_sequence(s1, s2));

return 0;

}

/* C++ program to count the common sub sequence of two strings */

#include <bits/stdc++.h>

using namespace std;

// Function to find common sub sequence in both strings

int count_common_sub_sequence(string s1, string s2)

{

int n1, n2;

n1 = s1.length();

n2 = s2.length();

int arr[n1+1][n2+1];

for (int i = 0; i <= n1; i++)

{

for (int j = 0; j <= n2; j++)

{

arr[i][j] = 0;

}

}

// for each character of S1

for (int i = 1; i <= n1; i++)

{

// for each character in S2

for (int j = 1; j <= n2; j++)

{

// if character are same in both the string

if (s1[i – 1] == s2[j – 1])

{

arr[i][j] = 1 + arr[i][j – 1] + arr[i – 1][j];

}

else

{

arr[i][j] = arr[i][j – 1] + arr[i – 1][j] – arr[i – 1][j – 1];

}

}

}

return arr[n1][n2];

}

int main()

{

string s1;

string s2;

cout << “\nEnter string 1 : “;

cin >> s1;

cout << “\nEnter string 2 : “;

cin >> s2;

cout << “\nCount of common sub sequence of two strings : ” << count_common_sub_sequence(s1, s2) << endl;

return 0;

}

/*Java program to count the common sub sequence of two strings */

import java.util.*;

public class Main

{

// Return the number of common subsequence in two strings

static int count_of_common_sub_sequence(String s1, String s2)

{

int n1 = s1.length();

int n2 = s2.length();

int arr[][] = new int [n1+1][n2+1];

char ch1,ch2 ;

for (int i = 0; i <= n1; i++)

{

for (int j = 0; j <= n2; j++)

{

arr[i][j] = 0;

}

}

// for each character of S1

for (int i = 1; i <= n1; i++) {

// for each character in S2

for (int j = 1; j <= n2; j++) {

ch1 = s1.charAt(i – 1);

ch2 = s2.charAt(j – 1);

// if character are same in both the string

if (ch1 == ch2)

arr[i][j] = 1 + arr[i][j – 1] + arr[i – 1][j];

else

arr[i][j] = arr[i][j – 1] + arr[i – 1][j] – arr[i – 1][j – 1];

}

}

return arr[n1][n2];

}

public static void main (String args[])

{

String s1;

String s2;

Scanner sc = new Scanner(System.in);

System.out.print(“\nEnter string 1 : “);

s1 = sc.next();

System.out.print(“\nEnter string 2 : “);

s2 = sc.next();

System.out.println(“\nCount of common sub sequence of two strings : ” + count_of_common_sub_sequence(s1, s2));

}

}

# Python program to count the common sub sequence of two strings

def count_common_sub_sequence(s1, s2):

n1 = len(s1)

n2 = len(s2)

arr = [[0 for i in range(n2 + 1)]

for i in range(n1 + 1)]

# for each character of S1

for i in range(1, n1 + 1):

# for each charcater in S2

for j in range(1, n2 + 1):

# If character are same in both the string

if (s1[i – 1] == s2[j – 1]):

arr[i][j] = (1 + arr[i][j – 1] +

arr[i – 1][j])

else:

arr[i][j] = (arr[i][j – 1] + arr[i – 1][j] –

arr[i – 1][j – 1])

return arr[n1][n2]

s1 = input(“Enter string 1 : “)

s2 = input(“Enter string 2 : “)

print(“\nCount of common sub sequence of two strings : “, count_common_sub_sequence(s1, s2))

**Output:**