# Write a Program to Count common subsequence in two strings

12 July 2022

Write a Program to Count common subsequence in two strings

If you are from 2023 batch student, Join our Telegram group for placement preparation and coming placement drive updates : https://t.me/talentbattle2023

# Description

Get two strings as the input from the user and then count the common subsequence in both the strings.

Input

Efgh

Ef

Output

Number of subsequences is: 3

C Program

#include <stdio.h>

#include <string.h>

int sequences(char str1[], char str2[])

{

int c1 = strlen(str1);

int c2 = strlen(str2);

int count[c1+1][c2+1];

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

{

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

{

count[i][j] = 0;

}

}

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

{

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

{

if(str1[i-1] == str2[j-1])

{

count[i][j] = 1 + count[i][j-1] + count[i-1][j];

}

else

{

count[i][j] = count[i][j-1] + count[i-1][j] - count[i-1][j-1];

}

}

}

return count[c1][c2];

}

int main()

{

char str1[10] ,str2[10];

printf("Enter first string: ");

scanf("%s",str1);

printf("Enter second string: ");

scanf("%s",str2);

printf("Number of subsequence is: %d ",sequences(str1, str2));

return 0;

}

C++ Program

#include <iostream>

#include <string.h>

using namespace std;

int sequences(char str1[], char str2[])

{

int c1 = strlen(str1);

int c2 = strlen(str2);

int count[c1+1][c2+1];

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

{

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

{

count[i][j] = 0;

}

}

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

{

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

{

if(str1[i-1] == str2[j-1])

{

count[i][j] = 1 + count[i][j-1] + count[i-1][j];

}

else

{

count[i][j] = count[i][j-1] + count[i-1][j] - count[i-1][j-1];

}

}

}

return count[c1][c2];

}

int main()

{

char str1[10] ,str2[10];

cout<<"Enter first string: ";

cin>>str1;

cout<<"Enter second string: ";

cin>>str2;

cout<<"Number of subsequence is: "<<sequences(str1, str2);

return 0;

}

Python

str1=input("Enter first string: ")

str2=input("Enter second string: ")

l1,l2=len(str1),len(str2)

count=[[0 for i in range(l2+1)] for i in range(l1+1)]

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

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

if(str1[i-1] == str2[j-1]):

count[i][j] = 1 + count[i][j-1] + count[i-1][j]

else:

count[i][j] = count[i][j-1] + count[i-1][j] - count[i-1][j-1]

print(count[l1][l2])

If you are from 2023 batch student, Join our Telegram group for placement preparation and coming placement drive updates : https://t.me/talentbattle2023