# Ninja's Frustrating Homework

Posted: 8 Jul, 2021
Difficulty: Ninja

## PROBLEM STATEMENT

#### Note :

``````Follow 0 based indexing.
Print the indices in sorted order.
``````

#### Input Format :

``````The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows.

The first line of each test case contains a string ‘S’ representing the string in the booklet.

The second line of each test case contains an integer N denoting the number of words in the diary.

The third line of each test case contains an array of strings of size ‘N’ representing the words in the diary.
``````

#### Output Format :

``````The output contains ‘N’ space-separated integers representing starting indices of ‘N’ number of words present in the diary.
``````

#### Note:

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

#### Constraints :

``````1 <= T <= 10
1 <= |S| <= 1000
1 <= N <= 30

Where |S| denotes the length of the given string ‘S’.
`````` Approach 1

The idea is to slide every word in ‘diary’ over ‘booklet’ string one by one and check for a match. If a match is found, then slide by 1 to check for subsequent matches.

Approach :

• First store the length of ‘booklet’ in a variable‘bookletLength’.
• Iterate the loop for all words of ‘diary’ with the help of an iterator pointer ‘i’.
• Store the length of each word of ‘diary’ in a variable ‘wordLength’.
• Make an iteration to slide the word of ‘diary’ one by one with the help of an iterator pointer ‘j’ from 0 to ‘bookletLength’ - ‘wordLength’.
• For the current index ‘j’ check for pattern matching with an iteration from 0 to ‘wordLength’ with an iterator pointer ‘k’.
• Check if booklet[j + k] is not equal to diary[i][k]. If this condition is true then exit the iteration.
• Check if k = ‘wordLength’ then push the index ‘i’ into the vector ‘ans’.
• Return ‘ans’ as the final answer.