 New update is available. Click here to update.

# String Maker

Last Updated: 10 Dec, 2020
Difficulty: Hard

## PROBLEM STATEMENT

#### As the answer could be large so return it after modulo 10 ^ 9 + 7.

##### For Example :
``````let A = a, B = ac, C = ac.

Now In this example, we can take whole string B to form C or take substring {a} and substring {c} from A and B, respectively to make C. Hence the answer is 2.
``````
##### Input Format :
``````The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then each test cases follow.

The first line of each test case contains a string ‘A’.

The Second line of the test case contains the string ‘B’.

The third line of the test case contains the string ‘C’.
``````
##### Output Format :
``````For each test case, print a single integer ‘ANS’ representing the number of ways.

Output for each test case will be printed in a separate line.
``````
##### Note :
``````You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
``````
##### Constraints :
``````1 <= T <= 5
1 <= |A|, |B|, |C| <= 100, where |S| represents the length of the String S.

Time limit: 1 sec
`````` ## Approach 1

The basic idea is to go through every element of the string A and B and check if the current element equals any element at some position in string C

The steps are as follows:

1. Create a function ‘recursion’ in which we will pass all the strings and their string length x, y, z for strings A, B, C, respectively.
2. In the ‘recursion’ function:
1. Iterate through the string A from x to 0:(say iterator be i):
1. If the current element at x of A is equal to the current element at z of C call the function for position x-1, y, z-1 and add it to the total ways.
2. Similarly, iterate through the string B from y to 0:(say iterator be i):
1. If the current element at y of B is equal to the current element at z of C call the function for position x, y-1, z-1 and add it to the total ways.
3. Return the total ways.
3. In the ‘Main’ function:
1. Call the ‘recursion’ function.