Prime

#### Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

#### Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

# Python program to Count Common Subsequence in two Strings

## Count Common Subsequence in two Strings

In this page we will learn how to write a code to count common subsequence in two strings using python. To do this we use Dynamic Programming(DP). Let’s see what is common subsequence means by taking an example.

##### Example:

Input:

• string1 = “ABC”
• string2 = “AB”

Output:

• 3

Explanation:

• common subsequence in “ABC” and “AB” is “A” , “B”, “AB”

## Algorithm:

• Initialize the variables.
• Accept the inputs.
• Iterate each character from  first string .
• Iterate each character from second string.
• Match these characters one by one.
• If they matches store the count.
• Print count.

## Python Code:

n=input()
m=input()
l1,l2=len(n),len(m)
cnt=[[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(n[i-1] == m[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]

print(cnt[l1][l2])

`ABCAB`

`3`