Find number of times a string occurs as a subsequence in given string | A Dynamic Programming based Java program to find the number of times the second string occurs in the first string , whether continuous or discontinuous ; Iterative DP function to find the number of times the second string occurs in the first string , whether continuous or discontinuous ; Create a table to store results of sub - problems ; If first string is empty ; If second string is empty ; Fill lookup [ ] [ ] in bottom up manner ; 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 last character are different , ignore last character of first string ; Driver Code
import java . io . * ; class GFG { static int count ( String a , String b ) { int m = a . length ( ) ; int n = b . length ( ) ; int lookup [ ] [ ] = new int [ m + 1 ] [ n + 1 ] ; for ( int i = 0 ; i <= n ; ++ i ) lookup [ 0 ] [ i ] = 0 ; for ( int i = 0 ; i <= m ; ++ i ) lookup [ i ] [ 0 ] = 1 ; for ( int i = 1 ; i <= m ; i ++ ) { for ( int j = 1 ; j <= n ; j ++ ) { if ( a . charAt ( i - 1 ) == b . charAt ( j - 1 ) ) lookup [ i ] [ j ] = lookup [ i - 1 ] [ j - 1 ] + lookup [ i - 1 ] [ j ] ; else lookup [ i ] [ j ] = lookup [ i - 1 ] [ j ] ; } } return lookup [ m ] [ n ] ; } public static void main ( String [ ] args ) { String a = " GeeksforGeeks " ; String b = " Gks " ; System . out . println ( count ( a , b ) ) ; } }