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])
