Link copied to clipboard. Share away!

Dismiss

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'.

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

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

×