Program to count the common sub sequence of two strings | faceprep

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:

count the common sub sequence of two strings