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
Related Articles

Ask Us Anything !