Question 4
Program to count common subsequence in two strings
Today we will learn program to count common subsequence in two strings. We will take two strings as an input, then we will 2-D ”cnt[][]” array that will store the count of common subsequence found. Now we will iterate each character of first string and each character of second string from of the string to its end , then if the characters matches we will check if the previous character of both string are same or not if they are same we will assign ”1 +cnt[i][j – 1] +cnt[i – 1][j]” to our 2D else we will assign ”cnt[i][j – 1] + cnt[i – 1][j] – cnt[i – 1][j – 1]” to our 2D array. As the iteration ends we will get our count.
Program to count common subsequence in two strings
C
C++
C
#include <stdio.h> #include <string.h> //Function to count the number of subsequences in the string. int countsequences(char str[], char str2[]) { int n1 = strlen(str); int n2 = strlen(str2); int cnt[n1+1][n2+1]; for (int i = 0; i <= n1; i++) { for (int j = 0; j <= n2; j++) { cnt[i][j] = 0; } } //Taking each character from first string. for (int i = 1; i <= n1; i++) { //Taking each character from second string. for (int j = 1; j <= n2; j++) { //If characters are same in both the string. if(str[i-1] == str2[j-1]) { cnt[i][j] = 1 + cnt[i][j-1] + cnt[i-1][j]; } else { cnt[i][j] = cnt[i][j-1] + cnt[i-1][j] - cnt[i-1][j-1]; } } } return cnt[n1][n2]; } //Main function for printing the result. int main() { char str[100] ,str2[100]; printf("Enter the first string: "); gets(str); printf("Enter string second: "); gets(str2); printf("Number of common subsequence is: %d ",countsequences(str, str2)); return 0; }
Output: Enter the first string: abc Enter string second: bc Number of common subsequence is: 3
C++
#include <iostream> #include <string.h> using namespace std; //Function to count the number of subsequences in the string int countsequences(char str[], char str1[]) { int l1 = strlen(str); int l2 = strlen(str1); int cnt[l1+1][l2+1]; for (int i = 0; i <= l1; i++) { for (int j = 0; j <= l2; j++) { cnt[i][j] = 0; } } //Taking each character from first string for (int i = 1; i <= l1; i++) { //Taking each character from second string for (int j = 1; j <= l2; j++) { //If characters are same in both the string if(str[i-1] == str1[j-1]) { cnt[i][j] = 1 + cnt[i][j-1] + cnt[i-1][j]; } else { cnt[i][j] = cnt[i][j-1] + cnt[i-1][j] - cnt[i-1][j-1]; } } } return cnt[l1][l2]; } //Main function for printing the result int main() { char str[100] ,str1[100]; cout<<"Enter the first string: "; cin>>str; cout<<"Enter the second string: "; cin>>str1; cout<<"Number of common subsequence is: "<<countsequences(str, str1); return 0; }
Output: Enter the first string: abc Enter the second string: ab Number of common subsequence is: 3
Login/Signup to comment
Simple python code:
A=input()
B=input()
K=[]
L=[]
c=0
for i in range(len(A)):
for j in range(i+1,len(A)+1):
K.append(A[i:j])
for i in range(len(B)):
for j in range(i+1,len(B)+1):
L.append(B[i:j])
for i in K:
if i in L:
c+=1
print(c)
Python code:
A=input()
B=input()
K=[]
L=[]
c=0
for i in range(len(A)):
for j in range(i+1,len(A)+1):
K.append(A[i:j])
for i in range(len(B)):
for j in range(i+1,len(B)+1):
L.append(B[i:j])
for i in K:
if i in L:
c+=1
print(c)
import itertools as it
def sub_seq(aa):
x, y = [], []
for i in range(1, len(aa) + 1):
x.append(list(it.combinations(aa, i)))
for i in x:
for j in i:
y.append(list(j))
return y
a = sub_seq(input())
b = sub_seq(input())
c = 0
for i in a:
if i in b:
c += 1
print(c)
#include
using namespace std;
int count_seq(string s1, string s2)
{
int x = s1.length();
int y = s2.length();
int cnt[x + 1][y + 1];
for (int i = 0; i < x + 1; i++)
{
for (int j = 0; j < y + 1; j++)
{
if (i == 0 || j == 0)
{
cnt[i][j] = 0;
}
}
}
for (int i = 1; i < x + 1; i++)
{
for (int j = 1; j > s1 >> s2;
cout << "Number of subsequences are: " << count_seq(s1, s2) << endl;
return 0;
}