Find number of times a string occurs as a subsequence in given string - GeeksforGeeks

Find number of times a string occurs as a subsequence in given string - GeeksforGeeks

Given two strings, find the number of times the second string occurs in the first string, whether continuous or discontinuous.

Examples:

Input:  
string a = "GeeksforGeeks"
string b = "Gks"

Output: 4

Explanation:  
The four strings are - (Check characters marked in bold)
GeeksforGeeks
GeeksforGeeks
GeeksforGeeks
GeeksforGeeks

If we carefully analyze the given problem, we can see that it can be easily divided into sub-problems. The idea is to process all characters of both strings one by one staring from either from left or right side. Let us traverse from right corner, there are two possibilities for every pair of character being traversed.

static int count(String a, String b)

{

    int m = a.length();

    int n = b.length();

  

    // Create a table to store

    // results of sub-problems

    int lookup[][] = new int[m + 1][n + 1];

  

    // If first string is empty

    for (int i = 0; i <= n; ++i)

        lookup[0][i] = 0;

  

    // If second string is empty

    for (int i = 0; i <= m; ++i)

        lookup[i][0] = 1;

  

    // Fill lookup[][] in 

    // bottom up manner

    for (int i = 1; i <= m; i++)

    {

        for (int j = 1; j <= n; j++)

        {

            // If last characters are 

            // same, we have two options -

            // 1. consider last characters 

            //    of both strings in solution

            // 2. ignore last character

            //    of first string

            if (a.charAt(i - 1) == b.charAt(j - 1))

                lookup[i][j] = lookup[i - 1][j - 1] + 

                               lookup[i - 1][j];

                  

            else

                // If last character are 

                // different, ignore last

                // character of first string

                lookup[i][j] = lookup[i - 1][j];

        }

    }

  

    return lookup[m][n];

}




m: Length of str1 (first string)
n: Length of str2 (second string)

If last characters of two strings are same, 
   1. We consider last characters and get count for remaining 
      strings. So we recur for lengths m-1 and n-1. 
   2. We can ignore last character of first string and 
      recurse for lengths m-1 and n.
else 
If last characters are not same, 
   We ignore last character of first string and 
   recurse for lengths m-1 and n.

int count(string a, string b, int m, int n)

{

    // If both first and second string is empty,

    // or if second string is empty, return 1

    if ((m == 0 && n == 0) || n == 0)

        return 1;

    // If only first string is empty and second

    // string is not empty, return 0

    if (m == 0)

        return 0;

    // If last characters are same

    // Recur for remaining strings by

    // 1. considering last characters of both strings

    // 2. ignoring last character of first string

    if (a[m - 1] == b[n - 1])

        return count(a, b, m - 1, n - 1) +

               count(a, b, m - 1, n);

    else

        // If last characters are different, ignore

        // last char of first string and recur for

        // remaining string

        return count(a, b, m - 1, n);

}

Read full article from Find number of times a string occurs as a subsequence in given string - GeeksforGeeks