Distinct Occurences

Moderate

0/80

Average time to solve is 15m

Contributed by

4 upvotes

Asked in companies

Problem statement

You are given two strings 'A' and 'B' of length 'N' and 'M' respectively, your task is to find the number of distinct occurrences of string 'B' in the string A as a subsequence.

Note:

1. A subsequence is a sequence generated from a string after deleting some characters of string without changing the order of remaining string characters.

2. 'A' and 'B' will be non-empty strings.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains two space-separated integers 'N' and 'M', the length of string 'A' and 'B' respectively.

The second line of each test case contains a string 'A'. 

The third line of each test case contains a string 'B'.

Output Format:

For each test case, return an integer denoting the number of distinct occurrences of 'B' in 'A' as a subsequence.

Note :

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= M, N <= 100

Time limit: 1 sec

Sample Input 1:

2
12 3
codingninjas
cij
2 1
aa
b

Sample Output 1:

2
0

Explanation of Sample Output 1:

In test case 1, Possible subsequences are: [c  i     j  ], [c      i j  ].

In test case 2, There is no possible subsequence.

Sample Input 2:

2
4 2
abcd
ac
6 3
banana
ban

Sample Output 2:

1
3

Explanation of Sample Output 2:

In test case 1, Possible subsequence is: [a c ].

In test case 2, Possible subsequences are: [ban], [ba  n ],[b   an ].

Console