Ninja's Frustrating Homework

Posted: 8 Jul, 2021
Difficulty: Ninja

PROBLEM STATEMENT

Try Problem

Ninja got a summer vacation homework in which he got a booklet containing a very long string and some set of words written in his diary for which he had to search all these words in that string booklet.

His teacher asked him to write all the starting indices for all the words written in the diary after searching that from the string booklet.

Ninja finds this work very frustrating. He tries to find some help from his neighbor and currently, you are the one who is his neighbor.

It is very time consuming to find every word in the string booklet manually. So you decide to design a code for that. Help Ninja!

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.
Try Problem