Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Webinars
About Us

Edit
Reply




Edit

Program to count the common sub sequence of two strings | FACE Prep

Published on 11 Mar 2020

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 get 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


C
C++
Java
Python 3

Output
Input - Enter string 1 : abcd Enter string 2 : abc Output - Count of common sub sequence of two strings : 7


Recommended Programs






If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in