Question 4

September 10, 2020

Program to count common subsequence in two strings

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

17 comments on “Question 4”


  • Shivansh

    JAVA Solution
    import java.io.*;
    import java.util.*;

    public class Main{
    public static void main(String[] args){
    Scanner scn = new Scanner(System.in);
    String str1 = scn.next();
    String str2 = scn.next();
    ArrayList res = getSubSequence(str1);
    ArrayList res1 = getSubSequence(str2);
    int len = 0;

    ArrayList temp = new ArrayList();
    ArrayList large = new ArrayList();

    if(res.size()>res1.size()){
    len = res1.size();
    temp = res1;
    large = res;
    }else {
    len = res.size();
    temp = res;
    large = res1;
    }
    int count=0;
    for(int i=0;i<len;i++){
    String s = temp.get(i);
    for(int j=0;j<large.size();j++){
    if(s.equals(large.get(j))){
    count++;
    }
    }
    }
    System.out.print(count-1);
    }

    public static ArrayList getSubSequence(String str){

    if(str.length()==0){
    ArrayList bres = new ArrayList();
    bres.add(“”);
    return bres;
    }

    char ch = str.charAt(0);
    String subs = str.substring(1);
    ArrayList rres = getSubSequence(subs);

    ArrayList nres = new ArrayList();

    for(String s: rres){
    nres.add(“”+s);
    }
    for(String s : rres){
    nres.add(ch+s);
    }
    return nres;
    }
    }


  • Darshil

    Python Code:
    def longcomsub(str1,str2):
    n1 = len(str1)
    n2 = len(str2)

    c = []

    for i in range(0,n1+1):
    temp = []
    for j in range(0,n2+1):
    temp.append(0)
    c.append(temp)

    for i in range(1,n1+1):
    for j in range(1,n2+1):
    if str1[i-1] == str2[j-1]:
    # c[i][j] = 1 + c[i-1][j-1]
    c[i][j] = 1 + c[i-1][j] + c[i][j-1]
    else:
    c[i][j] = c[i-1][j] + c[i][j-1] – c[i-1][j-1]
    return c[n1][n2]

    str1 = “abc”
    str2 = “bc”

    print(longcomsub(str1,str2))


  • Dhanush

    #Common subsequences in two given strings
    str1=input()
    str2=input()
    n1,n2=len(str1),len(str2)
    sorted1=sorted(str1)
    sorted2=sorted(str2)
    temp=[]
    for i in sorted1:
    for _ in range(n2):
    if i in sorted2:
    temp.append(i)
    else:
    continue
    temp=sorted(list(set(temp)))
    temp1=temp
    temp2=[]
    for i in range(len(temp)):
    for j in range(i+1,len(temp)):
    try:
    temp2.append(temp[i]+temp[j])
    except:
    pass
    for i in temp2:
    temp.append(i)
    var=”.join(temp1)
    temp.append(var)
    temp=list(set(temp))
    result=len(temp)
    print(result)


  • Avirup

    #include
    using namespace std;
    int main()
    {
    int i,j;
    string s,t;
    cin>>s>>t;
    const int len1=s.length();
    const int len2=t.length();
    int dp[len1+1][len2+1];
    for(i=0;i<len1+1;i++)
    {
    for(j=0;j<len2+1;j++)
    {
    if(i==0||j==0)
    {
    dp[i][j]=0;
    }
    else
    {
    if(s[i-1]==t[j-1])
    {
    dp[i][j]=dp[i-1][j]+dp[i][j-1]+1;
    }
    else
    {
    dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
    }
    }
    }
    }
    cout<<dp[len1][len2]<<endl;
    return 0;
    }


  • Gourav

    s1=’gouragv’
    s2=’raghuv’

    dp=[[0 for i in range (len(s2)+1)] for i in range (len(s1)+1)]

    for i in range (1,len(s1)+1):

    for j in range (1,len(s2)+1):

    if(s1[i-1]==s2[j-1]):
    dp[i][j]=1+dp[i-1][j-1]

    else:
    dp[i][j]=max(dp[i-1][j],dp[i][j-1])

    print(dp[len(s1)][len(s2)])


  • Gangadhar

    package com.code4you.common_subsequence;

    import java.util.Scanner;

    public class Solution {

    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(“Enter first string:\n”);
    String str1 = sc.nextLine();
    System.out.println(“Enter second string:\n”);
    String str2 = sc.nextLine();
    sc.close();

    countCommonSubsequence(str1,str2);
    }

    private static void countCommonSubsequence(String str1, String str2) {

    int str1Len = str1.length();
    int str2Len = str2.length();

    int[][] countArr = new int[str1Len+1][str2Len+1];

    for (int i = 1; i <= str1Len; i++) {
    for (int j = 1; j <= str2Len; j++) {
    if (str1.charAt(i-1) == str2.charAt(j-1)) {
    countArr[i][j] = 1+countArr[i-1][j]+countArr[i][j-1];
    }else{
    countArr[i][j] = countArr[i-1][j]+countArr[i][j-1]-countArr[i-1][j-1];
    }
    }
    }

    for (int i = 0; i < str1Len; i++) {
    for (int j = 0; j < str2Len; j++) {

    System.out.print(countArr[i][j]+" ");
    }
    System.out.println();
    }

    System.out.println(countArr[str1Len][str2Len]);
    }

    }

1 2